第四版的变化

Changes in the Fourth Edition

与第三版相比，PLP-4e 包括

In comparison to the third edition, PLP-4e includes

1. 新增了关于类型系统和复合类型的章节，取代了之前关于类型的单独章节

1. New chapters devoted to type systems and composite types, in place of the older single chapter on types

2. 更新了函数式编程的处理方式，并广泛涵盖了 OCaml

2. Updated treatment of functional programming, with extensive coverage of OCaml

3. 该领域变化的许多其他反映

3. Numerous other reflections of changes in the field

4. 受讲师反馈或对熟悉主题的重新思考启发而做出的改进

4. Improvements inspired by instructor feedback or a fresh consideration of familiar topics

此列表中的第 1 项可能是最明显的变化。第 7 章是以前版本中最长的，主题材料自然而然地被拆分。PLP-4e 重新组织了这些材料，让我们有机会更加明确地关注类型推断的主题，尤其是它在 ML 系列语言中的作用。它还促进了参数多态性材料的更新和重新组织，这些材料以前分散在几个不同的章节中。

Item 1 in this list is perhaps the most visible change. Chapter 7 was the longest in previous editions, and there is a natural split in the subject material. Reorganization of this material for PLP-4e afforded an opportunity to devote more explicit attention to the subject of type inference, and of its role in ML-family languages in particular. It also facilitated an update and reorganization of the material on parametric polymorphism, which was previously scattered across several different chapters and sections.

第 2 项反映了函数式技术在主流命令式语言中的日益普及，以及 SML、OCaml 和 Haskell 在教育和工业领域的日益突出地位。在整篇文章中，OCaml 现在与 Scheme 一样，都是函数式编程示例的来源。如上一段所述，ML 类型系统有一个扩展部分 (7.2.4) ，第 11.4 节包括 OCaml 概述，涵盖了相等和排序、绑定和 lambda 表达式、类型构造函数、模式匹配以及控制流和副作用。选择 OCaml 而不是 Haskell 作为 ML 系列示例反映了其在工业领域的突出地位，同时课堂经验表明——至少对于许多学生来说——在急切求值的背景下，最初接触函数式思维会更容易。对于那些希望我选择 Haskell 的同事，我深表歉意！

Item 2 reflects the increasing adoption of functional techniques into mainstream imperative languages, as well as the increasing prominence of SML, OCaml, and Haskell in both education and industry. Throughout the text, OCaml is now co-equal with Scheme as a source of functional programming examples. As noted in the previous paragraph, there is an expanded section (7.2.4) on the ML type system, and Section 11.4 includes an OCaml overview, with coverage of equality and ordering, bindings and lambda expressions, type constructors, pattern matching, and control flow and side effects. The choice of OCaml, rather than Haskell, as the ML-family exemplar reflects its prominence in industry, together with classroom experience suggesting that—at least for many students—the initial exposure to functional thinking is easier in the context of eager evaluation. To colleagues who wish I'd chosen Haskell, my apologies!

其他新材料（第 3 项）出现在整篇文章中。在适当的地方，都引用了最新语言和标准的特性，包括 C 和 C++11、Java 8、C# 5、Scala、Go、Swift、Python 3 和 HTML 5。第 3.6.4 节汇集了之前分散的 lambda 表达式介绍，并展示了如何将它们添加到各种命令式语言中。第 10.4.4 节补充了对象闭包，包括 C++11 的std::function和std::bind。第 c-5.4.5 节介绍了 x86-64 和 ARM 体系结构，以取代以前版本中使用的 x86-32 和 MIPS。使用这两种相同体系结构的示例随后出现在调用序列（9.2）和链接（15.6）部分。x86 调用序列的介绍继续依赖于gcc；ARM 案例研究使用 LLVM。第 8.5.3 节介绍了智能指针。第 9.3.1 节中出现了 R 值引用。第 9.6.2 节的图形示例中，JavaFX 取代了 Swing 。附录 A中新增了 Go、Lua、Rust、Scala 和 Swift 的条目。

Other new material (Item 3) appears throughout the text. Wherever appropriate, reference has been made to features of the latest languages and standards, including C & C++11, Java 8, C# 5, Scala, Go, Swift, Python 3, and HTML 5. Section 3.6.4 pulls together previously scattered coverage of lambda expressions, and shows how these have been added to various imperative languages. Complementary coverage of object closures, including C++11's std::function and std::bind, appears in Section 10.4.4. Section c-5.4.5 introduces the x86-64 and ARM architectures in place of the x86-32 and MIPS used in previous editions. Examples using these same two architectures subsequently appear in the sections on calling sequences (9.2) and linking (15.6). Coverage of the x86 calling sequence continues to rely on gcc; the ARM case study uses LLVM. Section 8.5.3 introduces smart pointers. R-value references appear in Section 9.3.1. JavaFX replaces Swing in the graphics examples of Section 9.6.2. Appendix A has new entries for Go, Lua, Rust, Scala, and Swift.

最后，第 4 项包含对文本几乎每个部分的改进。更新较多的主题包括 FOLLOW 和 PREDICT 集（第 2.3.3 节）；Wirth 的递归下降错误恢复算法（第 c-2.3.5 节）；重载（第 3.5.2 节）；模块（第 3.3.4 节）；鸭子类型（第 7.3 节）；记录和变体（第 8.1 节）；侵入式列表（从第 10 章的运行示例中删除）；静态字段和方法（第 10.2.2 节）；混合继承（从配套站点移回正文，并更新以涵盖 Scala 特征和 Java 8 默认方法）；多核处理器（第 13 章的普遍变化）；移相器（第 13.3.1 节）；内存模型（第 13.3.3 节）；信号量（第 13.3.5 节）；未来（第 13.4.5 节）；GIMPLE 和 RTL（第 c-15.2.1节）；QEMU（第 16.2.2 节）；DWARF（第 16.3.2 节）；以及语言谱系（图 A.1）。

Finally, Item 4 encompasses improvements to almost every section of the text. Among the more heavily updated topics are FOLLOW and PREDICT sets (Section 2.3.3); Wirth's error recovery algorithm for recursive descent (Section c-2.3.5); overloading (Section 3.5.2); modules (Section 3.3.4); duck typing (Section 7.3); records and variants (Section 8.1); intrusive lists (removed from the running example of Chapter 10); static fields and methods (Section 10.2.2); mix-in inheritance (moved from the companion site back into the main text, and updated to cover Scala traits and Java 8 default methods); multicore processors (pervasive changes to Chapter 13); phasers (Section 13.3.1); memory models (Section 13.3.3); semaphores (Section 13.3.5); futures (Section 13.4.5); GIMPLE and RTL (Section c-15.2.1); QEMU (Section 16.2.2); DWARF (Section 16.3.2); and language genealogy (Figure A.1).

为了容纳新材料，一些主题的覆盖范围已被压缩甚至删除。例如模块（第 3 章和第 10 章）、变体记录和 with 语句（第 8 章）以及元循环解释（第 11 章）。附加材料（尤其是公共语言基础结构 (CLI)）已移至配套站点。在整篇文章中，来自不再广泛使用的语言的示例已在适当的情况下用更新的等效语言替换。几乎所有剩余的对 Pascal 和 Modula 的引用都只是历史性的。对 Occam 和 Tcl 的大部分介绍也已被删除。

To accommodate new material, coverage of some topics has been condensed or even removed. Examples include modules (Chapters 3 and 10), variant records and with statements (Chapter 8), and metacircular interpretation (Chapter 11). Additional material—the Common Language Infrastructure (CLI) in particular—has moved to the companion site. Throughout the text, examples drawn from languages no longer in widespread use have been replaced with more recent equivalents wherever appropriate. Almost all remaining references to Pascal and Modula are merely historical. Most coverage of Occam and Tcl has also been dropped.

总体而言，印刷文本增加了约 40 页。增加了 5 个“设计与实现”边栏、35 个编​​号示例以及约 25 个新的章末练习和探索。我们投入了大量精力来创建一致且全面的索引。与之前的版本一样，Morgan Kaufmann 一直致力于以合理的价格提供权威文本：PLP-4e 比竞争替代品便宜得多，但内容更丰富、更全面。

Overall, the printed text has grown by roughly 40 pages. There are 5 more “Design & Implementation” sidebars, 35 more numbered examples, and about 25 new end-of-chapter exercises and explorations. Considerable effort has been invested in creating a consistent and comprehensive index. As in earlier editions, Morgan Kaufmann has maintained its commitment to providing definitive texts at reasonable cost: PLP-4e is far less expensive than competing alternatives, but larger and more comprehensive.

配套网站

The Companion Site

为了尽量减少文本的物理尺寸，为新材料腾出空间，并让学生在浏览时专注于基础知识，可以在配套网站上找到超过 350 页的更高级或外围材料：booksite.elsevier.com/web/9780124104099。每个配套网站 (CS) 部分在正文中都由主题的简短介绍和总结省略材料的“更深入”段落表示。

To minimize the physical size of the text, make way for new material, and allow students to focus on the fundamentals when browsing, over 350 pages of more advanced or peripheral material can be found on a companion web site: booksite.elsevier.com/web/9780124104099. Each companion-site (CS) section is represented in the main text by a brief introduction to the subject and an “In More Depth” paragraph that summarizes the elided material.

请注意，将材料放在配套网站上并不构成对其技术重要性的判断。它只是反映了一个事实，即值得介绍的材料比一卷书或一学期课程所能容纳的要多。由于偏好和教学大纲各不相同，大多数教师可能希望从 CS 中指定阅读材料，并且大多数教师不会指定印刷文本的某些部分。我的目的是保留印刷版中可能在最多课程中涵盖的材料。

Note that placement of material on the companion site does not constitute a judgment about its technical importance. It simply reflects the fact that there is more material worth covering than will fit in a single volume or a single-semester course. Since preferences and syllabi vary, most instructors will probably want to assign reading from the CS, and most will refrain from assigning certain sections of the printed text. My intent has been to retain in print the material that is likely to be covered in the largest number of courses.

CS 中还包括指向在线资源的指针和文本中所有重要代码片段的可编译副本（超过二十种语言）。

Also included on the CS are pointers to on-line resources and compilable copies of all significant code fragments found in the text (in more than two dozen languages).

设计与实现侧边栏

Design & Implementation Sidebars

与其前身一样，PLP-4e 非常重视语言设计对实现选项的限制，以及预期实现对语言设计的影响。其中许多联系和相互作用在 140 个“设计与实现”边栏中进行了重点介绍。边栏 1.1 中有更详细的介绍。附录 B中有编号列表。

Like its predecessors, PLP-4e places heavy emphasis on the ways in which language design constrains implementation options, and the ways in which anticipated implementations have influenced language design. Many of these connections and interactions are highlighted in some 140 “Design & Implementation” sidebars. A more detailed introduction appears in Sidebar 1.1. A numbered list appears in Appendix B.

编号和标题示例

Numbered and Titled Examples

PLP-4e 中的示例与演示流程紧密结合。为了便于查找特定示例、记住其内容并在其他上下文中引用它们，每个示例的编号和标题都显示在边注中。正文和 CS 中有 1000 多个此类示例。详细列表见附录C。

Examples in PLP-4e are intimately woven into the flow of the presentation. To make it easier to find specific examples, to remember their content, and to refer to them in other contexts, a number and a title for each is displayed in a marginal note. There are over 1000 such examples across the main text and the CS. A detailed list appears in Appendix C.

锻炼计划

Exercise Plan

复习题在正文中每隔大约 10 页出现一次，位于主要章节的末尾。这些复习题直接基于前面的内容，并有简短、直接的答案。

Review questions appear throughout the text at roughly 10-page intervals, at the ends of major sections. These are based directly on the preceding material, and have short, straightforward answers.

每章末尾都有更详细的问题。这些问题分为练习和探索。前者通常比每节复习问题更具挑战性，适合家庭作业或简短的项目。后者更开放，需要网络或图书馆研究、大量时间投入或形成主观意见。注册教师可以从受密码保护的网站获取许多练习（但不包括探索）的解决方案：请访问textbooks.elsevier.com/web/9780124104099。

More detailed questions appear at the end of each chapter. These are divided into Exercises and Explorations. The former are generally more challenging than the per-section review questions, and should be suitable for homework or brief projects. The latter are more open-ended, requiring web or library research, substantial time commitment, or the development of subjective opinion. Solutions to many of the exercises (but not the explorations) are available to registered instructors from a password-protected web site: visit textbooks.elsevier.com/web/9780124104099.

如何使用本书

How to Use the Book

《编程语言语用学》涵盖了计算机课程 2013报告 [ SR13 ]中 PL“知识单元”的几乎所有材料。本书的设计对象是罗彻斯特大学的语言课程，该课程实际上是报告中的特色“课程范例”之一（第 369-371 页）。图 1说明了文本中的几种可能路径。

Programming Language Pragmatics covers almost all of the material in the PL “knowledge units” of the Computing Curricula 2013 report [SR13]. The languages course at the University of Rochester, for which this book was designed, is in fact one of the featured “course exemplars” in the report (pp. 369–371). Figure 1illustrates several possible paths through the text.

对于自学或全年课程（图 1中的F轨道），我建议从头到尾学习本书，在遇到每个“更深入”部分时转向配套网站。罗切斯特的一学期课程（R轨道）也涵盖了本书的大部分内容，但遗漏了大部分 CS章节，以及自下而上的解析（2.3.4）、逻辑语言（第 12 章）和第 15 章（构建可运行程序）和第 16 章（运行时程序管理）的后半部分。请注意，函数式编程（特别是第 11 章）的材料可以用 OCaml 或 Scheme 来教授。

For self-study, or for a full-year course (track F in Figure 1), I recommend working through the book from start to finish, turning to the companion site as each “In More Depth” section is encountered. The one-semester course at Rochester (track R) also covers most of the book, but leaves out most of the CS sections, as well as bottom-up parsing (2.3.4), logic languages (Chapter 12), and the second halves of Chapters 15 (Building a Runnable Program) and 16 (Runtime Program Management). Note that the material on functional programming (Chapter 11 in particular) can be taught in either OCaml or Scheme.

某些章节（2、4、5、15、16、17 ）比其他章节更侧重于实现问题。这些章节可以相对于更面向设计的章节进行一定程度的重新排序。许多学生已经熟悉第 5 章中的大部分材料，很可能来自计算机组织课程；因此将本章放在配套网站上。一些学生可能还熟悉第2 章中的部分材料，也许来自自动机理论课程。本章的大部分内容也可以快速阅读，也许停下来思考一些实际问题，如从语法错误中恢复，或者扫描器与经典有限自动机的不同之处。

Some chapters (2, 4, 5, 15,16, 17) have a heavier emphasis than others on implementation issues. These can be reordered to a certain extent with respect to the more design-oriented chapters. Many students will already be familiar with much of the material in Chapter 5, most likely from a course on computer organization; hence the placement of the chapter on the companion site. Some students may also be familiar with some of the material in Chapter 2, perhaps from a course on automata theory. Much of this chapter can then be read quickly as well, pausing perhaps to dwell on such practical issues as recovery from syntax errors, or the ways in which a scanner differs from a classical finite automaton.

传统的编程语言课程（图 1中的P轨道）可能会省略所有扫描和解析，以及第 4 章的全部内容。它还会从头到尾淡化面向实现的材料。取而代之的是，它可以添加面向设计的 CS 部分，如多重继承（10.6）、Smalltalk（10.7.1）、lambda 演算（11.7）和谓词演算（12.3）。

A traditional programming languages course (track P in Figure 1) might leave out all of scanning and parsing, plus all of Chapter 4. It would also de-emphasize the more implementation-oriented material throughout. In place of these, it could add such design-oriented CS sections as multiple inheritance (10.6), Smalltalk (10.7.1), lambda calculus (11.7), and predicate calculus (12.3).

一些学校还使用 PLP 作为编译器入门课程（图 1中的C部分）。典型的教学大纲省略了第 III 部分（第 11 章至第 14 章）的大部分内容，并且从头到尾都淡化了更注重设计的材料。取而代之的是，它包括了所有扫描和解析内容、第 15 章至第 17章，以及略有不同的其他 CS 部分。

PLP has also been used at some schools for an introductory compiler course (track C in Figure 1). The typical syllabus leaves out most of Part III (Chapters 11 through 14), and de-emphasizes the more design-oriented material throughout. In place of these, it includes all of scanning and parsing, Chapters 15 through 17, and a slightly different mix of other CS sections.

对于采用学季制的学校，一个有吸引力的选择是提供一门为期一个学季的入门课程和两门可选的后续课程（图 1中的Q轨道）。入门学季可能涵盖第 1、3、6、7 和 8 章的主要（非 CS）部分，以及第2和9 章的前半部分。面向语言的后续学季可能涵盖第 9 章的其余部分、全部第 III 部分、第 6 至第 9 章的 CS 部分，以及可能的形式语义、类型理论或其他相关主题的补充材料。面向编译器的后续学季可能涵盖第 2 章的其余部分；第 4至第 5 章和第15至第 17章、第 3和第 9至第10章的 CS 部分，以及可能关于自动代码生成、积极代码改进、编程工具等的补充材料。

For a school on the quarter system, an appealing option is to offer an introductory one-quarter course and two optional follow-on courses (track Q in Figure 1). The introductory quarter might cover the main (non-CS) sections of Chapters 1, 3, 6, 7, and 8, plus the first halves of Chapters 2 and 9. A language-oriented follow-on quarter might cover the rest of Chapter 9, all of Part III, CS sections from Chapters 6 through 9, and possibly supplemental material on formal semantics, type theory, or other related topics. A compiler-oriented follow-on quarter might cover the rest of Chapter 2; Chapters 4–5 and 15–17, CS sections from Chapters 3 and 9–10, and possibly supplemental material on automatic code generation, aggressive code improvement, programming tools, and so on.

无论以何种方式阅读本书，我都假定读者已经对至少一种命令式语言有了丰富的使用经验。具体是哪种语言并不重要。书中的示例来自多种语言，但都附有足够的注释和其他讨论，即使没有相关经验的读者也应该能够轻松理解。附录 A中提供了 60 多种不同语言的单段介绍。如果需要，算法将以非正式的伪代码形式呈现，这些伪代码应该是不言自明的。真正的编程语言代码采用“打字机”字体。伪代码采用无衬线字体。

Whatever the path through the text, I assume that the typical reader has already acquired significant experience with at least one imperative language. Exactly which language it is shouldn't matter. Examples are drawn from a wide variety of languages, but always with enough comments and other discussion that readers without prior experience should be able to understand easily. Single-paragraph introductions to more than 60 different languages appear in Appendix A. Algorithms, when needed, are presented in an informal pseudocode that should be self-explanatory. Real programming language code is set in “typewriter“ font. Pseudocode is set in a sans-serif font.

补充材料

Supplemental Materials

除了补充章节外，配套网站还包含所有非平凡示例的完整源代码，以及书中所有已知错误的列表。其他资源可在线获取，网址为textbooks.elsevier.com/web/9780124104099。对于采用该文本的教师，密码保护页面可访问

In addition to supplemental sections, the companion site contains complete source code for all nontrivial examples, and a list of all known errors in the book. Additional resources are available on-line at textbooks.elsevier.com/web/9780124104099. For instructors who have adopted the text, a password-protected page provides access to

■ 书中所有图表的 PDF 源代码均可编辑

■ Editable PDF source for all the figures in the book

■ 可编辑的 PowerPoint 幻灯片

■ Editable PowerPoint slides

■ 大部分练习的答案

■ Solutions to most of the exercises

■ 对大型项目的建议

■ Suggestions for larger projects

第四版致谢

Acknowledgments for the Fourth Edition

在编写第四版的过程中，我得到了很多人的慷慨帮助。许多人对第三版提供了勘误表或其他反馈，其中包括 Yacine Belkadi、Björn Brandenburg、Bob Cochran、Daniel Crisman、Marcelino Debajo、Chen Ding、Peter Drake、Michael Edgar、Michael Glass、Sergio Gomes、Allan Gottlieb、Hossein Hadavi、Chris Hart、Thomas Helmuth、Wayne Heym、Scott Hoge、Kelly Jones、Ahmed Khademzadeh、Eleazar Enrique Leal、Kyle Liddell、Annie Liu、Hao Luo、Dirk Müller、Holger Peine、Andreas Priesnitz、Mikhail Prokharau、Harsh Raju 和 Jingguo Yao。我还非常感谢在之前版本中感谢的许多人，以及使这些版本取得成功的评论者、采用者和读者。

In preparing the fourth edition, I have been blessed with the generous assistance of a very large number of people. Many provided errata or other feedback on the third edition, among them Yacine Belkadi, Björn Brandenburg, Bob Cochran, Daniel Crisman, Marcelino Debajo, Chen Ding, Peter Drake, Michael Edgar, Michael Glass, Sergio Gomes, Allan Gottlieb, Hossein Hadavi, Chris Hart, Thomas Helmuth, Wayne Heym, Scott Hoge, Kelly Jones, Ahmed Khademzadeh, Eleazar Enrique Leal, Kyle Liddell, Annie Liu, Hao Luo, Dirk Müller, Holger Peine, Andreas Priesnitz, Mikhail Prokharau, Harsh Raju, and Jingguo Yao. I also remain indebted to the many individuals acknowledged in previous editions, and to the reviewers, adopters, and readers who made those editions a success.

第四版的匿名审阅者提供了大量有用的建议；我向你们所有人表示感谢！特别感谢麻省理工学院的 Adam Chlipala 对函数式编程内容的详细而深刻的建议。我还要感谢 Nelson Beebe（犹他大学），他指出编译器不能安全地对可能是 NaN 的浮点数使用整数比较；感谢 Dan Scarafoni 提示我在生成 PREDICT 集的算法中区分符号的 FIRST/EPS 和字符串的 FIRST/EPS；感谢 Dave Musicant 建议改进深度绑定的描述；感谢 Allan Gottlieb（纽约大学）对 Ada 语义的几个关键澄清；感谢 Benjamin Kowarsch 对 Objective-C 的类似澄清。所有这些领域中仍然存在的问题完全是我自己的问题。

Anonymous reviewers for the fourth edition provided a wealth of useful suggestions; my thanks to all of you! Special thanks to Adam Chlipala of MIT for his detailed and insightful suggestions on the coverage of functional programming. My thanks as well to Nelson Beebe (University of Utah) for pointing out that compilers cannot safely use integer comparisons for floating-point numbers that may be NaNs; to Dan Scarafoni for prompting me to distinguish between FIRST/EPS of symbols and FIRST/EPS of strings in the algorithm to generate PREDICT sets; to Dave Musicant for suggested improvements to the description of deep binding; to Allan Gottlieb (NYU) for several key clarifications regarding Ada semantics; and to Benjamin Kowarsch for similar clarifications regarding Objective-C. Problems that remain in all these areas are entirely my own.

在编写第四版时，我借鉴了在罗彻斯特大学向高年级本科生教授此教材的 25 年经验。我感谢所有学生的热情和反馈。我还要感谢我的同事和研究生，以及系里的行政、秘书和技术人员，感谢他们提供了如此支持和高效的工作环境。最后，我要感谢 David Padua，自从读研究生以来，我一直很钦佩他的作品；我很荣幸他能成为序言的作者。

In preparing the fourth edition, I have drawn on 25 years of experience teaching this material to upper-level undergraduates at the University of Rochester. I am grateful to all my students for their enthusiasm and feedback. My thanks as well to my colleagues and graduate students, and to the department's administrative, secretarial, and technical staff for providing such a supportive and productive work environment. Finally, my thanks to David Padua, whose work I have admired since I was in graduate school; I am deeply honored to have him as the author of the Foreword.

正如之前的版本一样，与 Morgan Kaufmann 的员工合作是一种真正的乐趣，无论是在专业层面还是个人层面。我特别感谢高级开发编辑 Nate McFadden，他以无尽的耐心、幽默感和对细节的敏锐眼光指导了这一版和前两版；感谢管理本书制作的 Mohana Natarajan；感谢出版商 Todd Green，他在更大的 Elsevier 世界中保持了 Morgan Kauffman 印记的个人风格。

As they were on previous editions, the staff at Morgan Kaufmann has been a genuine pleasure to work with, on both a professional and a personal level. My thanks in particular to Nate McFadden, Senior Development Editor, who shepherded both this and the previous two editions with unfailing patience, good humor, and a fine eye for detail; to Mohana Natarajan, who managed the book's production; and to Todd Green, Publisher, who upholds the personal touch of the Morgan Kauffman imprint within the larger Elsevier universe.

最重要的是，我要感谢我的妻子凯利，感谢她在我写作和修改的漫长岁月中给予我的耐心和支持。计算机是一项很好的职业，但家庭才是最重要的。

Most important, I am indebted to my wife, Kelly, for her patience and support through endless months of writing and revising. Computing is a fine profession, but family is what really matters.

迈克尔·斯科特

Michael L. Scott

纽约州罗切斯特

Rochester, NY

2015 年 8 月

August 2015

1.1 语言设计的艺术

1.1 The Art of Language Design

如今，高级编程语言有数千种，而且新的语言还在不断涌现。为什么会有这么多呢？有几种可能的答案：

Today there are thousands of high-level programming languages, and new ones continue to emerge. Why are there so many? There are several possible answers:

演化。计算机科学是一门年轻的学科；我们一直在寻找更好的方法来做事。20 世纪 60 年代末和 70 年代初，“结构化编程”发生了一场革命，Fortran、Cobol 和 Basic ³等语言的基于goto的控制流让位于while循环、case (switch)语句和类似的高级结构。20 世纪 80 年代末，Algol、Pascal 和 Ada 等语言的嵌套块结构开始让位于 Smalltalk、C++、Eiffel 等语言的面向对象结构，以及十年后的 Java 和 C#。最近，Python 和 Ruby 等脚本语言开始取代更传统的编译语言，至少在快速开发方面是如此。

Evolution. Computer science is a young discipline; we're constantly finding better ways to do things. The late 1960s and early 1970s saw a revolution in “structured programming,” in which the goto-based control flow of languages like Fortran, Cobol, and Basic³ gave way to while loops, case (switch) statements, and similar higher-level constructs. In the late 1980s the nested block structure of languages like Algol, Pascal, and Ada began to give way to the object-oriented structure of languages like Smalltalk, C++, Eiffel, and—a decade later—Java and C#. More recently, scripting languages like Python and Ruby have begun to displace more traditional compiled languages, at least for rapid development.

特殊用途。有些语言是为特定问题领域设计的。各种 Lisp 方言适合处理符号数据和复杂数据结构。Icon 和 Awk 适合处理字符串。C 适合低级系统编程。Prolog 适合推理数据之间的逻辑关系。这些语言中的每一种都可以成功地用于更广泛的任务，但重点显然在于专业性。

Special Purposes. Some languages were designed for a specific problem domain. The various Lisp dialects are good for manipulating symbolic data and complex data structures. Icon and Awk are good for manipulating character strings. C is good for low-level systems programming. Prolog is good for reasoning about logical relationships among data. Each of these languages can be used successfully for a wider range of tasks, but the emphasis is clearly on the specialty.

个人偏好。不同的人喜欢不同的东西。编程的狭隘性很大程度上只是个人品味的问题。有些人喜欢 C 的简洁性，有些人讨厌它。有些人觉得递归思考很自然，而另一些人则喜欢迭代。有些人喜欢使用指针，而另一些人则喜欢 Lisp、Java 和 ML 的隐式解引用。个人偏好的强烈和多样性使得不可能有人能开发出一种普遍接受的编程语言。

Personal Preference. Different people like different things. Much of the parochialism of programming is simply a matter of taste. Some people love the terseness of C; some hate it. Some people find it natural to think recursively; others prefer iteration. Some people like to work with pointers; others prefer the implicit dereferencing of Lisp, Java, and ML. The strength and variety of personal preference make it unlikely that anyone will ever develop a universally acceptable programming language.

当然，有些语言比其他语言更成功。在众多已设计的语言中，只有几十种被广泛使用。什么使一种语言成功？同样，有几个答案：

Of course, some languages are more successful than others. Of the many that have been designed, only a few dozen are widely used. What makes a language successful? Again there are several answers:

表达能力。人们经常听到一种语言比另一种语言更“强大”的说法，尽管从形式数学意义上讲，它们都是图灵完备— 每种语言都可以用来实现任意算法，尽管用起来有些别扭。不过，语言特性显然对程序员编写清晰、简洁、可维护的代码的能力有着巨大的影响，尤其是对于非常大的系统。例如，早期版本的 Basic 和 C++ 之间没有可比性。本书主要关注的是那些有助于表达能力的因素 — 尤其是抽象功能。

Expressive Power. One commonly hears arguments that one language is more “powerful” than another, though in a formal mathematical sense they are all Turing complete—each can be used, if awkwardly, to implement arbitrary algorithms. Still, language features clearly have a huge impact on the programmer's ability to write clear, concise, and maintainable code, especially for very large systems. There is no comparison, for example, between early versions of Basic on the one hand, and C++ on the other. The factors that contribute to expressive power—abstraction facilities in particular—are a major focus of this book.

新手易用。虽然 Basic 很容易上手，但不可否认它的成功。成功的一部分原因在于其“学习曲线”非常低。多年来，入门级编程语言课程都教授 Pascal，因为至少与其他“严肃”语言相比，它紧凑且易于学习。世纪之交后不久，Java 开始扮演类似的角色；尽管它比 Pascal 复杂得多，但比 C++ 等语言更简单。为了重新追求简单性，近年来一些入门课程已转向 Python 等脚本语言。

Ease of Use for the Novice. While it is easy to pick on Basic, one cannot deny its success. Part of that success was due to its very low “learning curve.” Pascal was taught for many years in introductory programming language courses because, at least in comparison to other “serious” languages, it was compact and easy to learn. Shortly after the turn of the century, Java came to play a similar role; though substantially more complex than Pascal, it is simpler than, say, C++. In a renewed quest for simplicity, some introductory courses in recent years have turned to scripting languages like Python.

易于实现。除了学习难度低之外，Basic 的成功还在于它能够在资源有限的微型机器上轻松实现。出于类似的原因，Forth 拥有一小群忠实的追随者。可以说，Pascal 成功最重要的一个因素是其设计者 Niklaus Wirth 开发了一种简单、可移植的语言实现，并将其免费提供给世界各地的大学（参见示例 1.15）。4 ^Java和 Python 的设计者采取了类似的措施，让几乎所有需要的人都可以免费使用他们的语言。

Ease of Implementation. In addition to its low learning curve, Basic was successful because it could be implemented easily on tiny machines, with limited resources. Forth had a small but dedicated following for similar reasons. Arguably the single most important factor in the success of Pascal was that its designer, Niklaus Wirth, developed a simple, portable implementation of the language, and shipped it free to universities all over the world (see Example 1.15).⁴ The Java and Python designers took similar steps to make their language available for free to almost anyone who wants it.

标准化。几乎每种广泛使用的语言都有一个官方的国际标准或（对于几种脚本语言而言）一个单一的规范实现；在后一种情况下，规范实现几乎总是用具有标准的语言编写的。标准化（包括语言和大量库的标准化）是确保代码跨平台可移植性的唯一真正有效的方法。Pascal 的标准相对贫乏，缺少许多程序员认为必不可少的几个功能（单独编译、字符串、静态初始化、随机访问 I/O），这至少是该语言在 20 世纪 80 年代失宠的部分原因。其中许多功能由不同的供应商以不同的方式实现。

Standardization. Almost every widely used language has an official international standard or (in the case of several scripting languages) a single canonical implementation; and in the latter case the canonical implementation is almost invariably written in a language that has a standard. Standardization—of both the language and a broad set of libraries—is the only truly effective way to ensure the portability of code across platforms. The relatively impoverished standard for Pascal, which was missing several features considered essential by many programmers (separate compilation, strings, static initialization, random-access I/O), was at least partially responsible for the language's drop from favor in the 1980s. Many of these features were implemented in different ways by different vendors.

开源。当今大多数编程语言都至少有一个开源编译器或解释器，但有些语言（尤其是 C 语言）与其他语言相比，与自由分发、同行评审、社区支持的计算联系更为密切。C 语言最初是在 20 世纪早期开发的。20 世纪 70 年代，贝尔实验室的 Dennis Ritchie 和 Ken Thompson 开发了 C 语言，⁵与最初的 Unix 操作系统的设计相结合。多年来，Unix 逐渐发展成为世界上最具可移植性的操作系统——学术计算机科学的首选操作系统——而 C 语言与它密切相关。随着 C 语言的标准化，该语言开始在各种各样的其他平台上使用。领先的开源操作系统 Linux 就是用 C 语言编写的。截至 2015 年 6 月，C 语言及其后代占据了各种与语言相关的在线内容的一半以上，包括网页参考、图书销售、招聘信息和开源存储库更新。

Open Source. Most programming languages today have at least one open-source compiler or interpreter, but some languages—C in particular—are much more closely associated than others with freely distributed, peer-reviewed, community-supported computing. C was originally developed in the early 1970s by Dennis Ritchie and Ken Thompson at Bell Labs,⁵ in conjunction with the design of the original Unix operating system. Over the years Unix evolved into the world's most portable operating system—the OS of choice for academic computer science—and C was closely associated with it. With the standardization of C, the language became available on an enormous variety of additional platforms. Linux, the leading open-source operating system, is written in C. As of June 2015, C and its descendants account for well over half of a variety oflanguage-related on-line content, including web page references, book sales, employment listings, and open-source repository updates.

优秀的编译器。Fortran 的成功很大程度上要归功于极其优秀的编译器。这在一定程度上是历史的偶然。Fortran 的存在时间比其他任何语言都要长，各大公司都投入了大量的时间和金钱来开发能够生成非常快的代码的编译器。然而，这也是一个语言设计的问题：Fortran 90 之前的 Fortran 方言缺少递归和指针，这些功能大大增加了生成快速代码的任务的复杂度（至少对于那些没有它们也能以合理的方式编写的程序而言！）。同样，一些语言（例如 Common Lisp）之所以成功，部分原因是它们的编译器和支持工具能够出色地帮助程序员管理非常大的项目。

Excellent Compilers. Fortran owes much of its success to extremely good compilers. In part this is a matter of historical accident. Fortran has been around longer than anything else, and companies have invested huge amounts of time and money in making compilers that generate very fast code. It is also a matter of language design, however: Fortran dialects prior to Fortran 90 lacked recursion and pointers, features that greatly complicate the task of generating fast code (at least for programs that can be written in a reasonable fashion without them!). In a similar vein, some languages (e.g., Common Lisp) have been successful in part because they have compilers and supporting tools that do an unusually good job of helping the programmer manage very large projects.

经济、赞助和惯性。最后，除了技术优势之外，还有其他因素对成功有很大影响。强大赞助商的支持就是其中之一。PL/I 至少在初步估计中，其生命力归功于 IBM。Cobol 和 Ada 的生命力归功于美国国防部。C# 的生命力归功于微软。近年来，Objective-C 作为 iPhone 和 iPad 应用程序的官方语言，人气飙升。在生命周期的另一端，一些语言在出现“更好”的替代方案后仍被广泛使用，因为有大量已安装的软件和程序员专业知识，而替换这些语言的成本太高。例如，世界上许多金融基础设施仍然主要在 Cobol 中运行。

Economics, Patronage, and Inertia. Finally, there are factors other than technical merit that greatly influence success. The backing of a powerful sponsor is one. PL/I, at least to first approximation, owed its life to IBM. Cobol and Ada owe their life to the U. S. Department of Defense. C# owes its life to Microsoft. In recent years, Objective-C has enjoyed an enormous surge in popularity as the official language for iPhone and iPad apps. At the other end of the life cycle, some languages remain widely used long after “better” alternatives are available, because of a huge base of installed software and programmer expertise, which would cost too much to replace. Much of the world's financial infrastructure, for example, still functions primarily in Cobol.

显然，没有哪个单一因素可以决定一种语言是否“好”。在研究编程语言时，我们需要从多个角度考虑问题。特别是，我们需要考虑程序员和语言实现者的观点。有时这些观点会一致，比如对执行速度的渴望。然而，通常会出现冲突和权衡，因为功能的概念吸引力与其实现成本相平衡。当实现不仅对使用该功能的程序施加成本，而且对不使用此功能的程序也施加成本时，权衡就变得特别棘手。

Clearly no single factor determines whether a language is “good.” As we study programming languages, we shall need to consider issues from several points of view. In particular, we shall need to consider the viewpoints of both the programmer and the language implementor. Sometimes these points of view will be in harmony, as in the desire for execution speed. Often, however, there will be conflicts and tradeoffs, as the conceptual appeal of a feature is balanced against the cost of its implementation. The tradeoff becomes particularly thorny when the implementation imposes costs not only on programs that use the feature, but also on programs that do not.

在计算发展的早期，实现者的观点占主导地位。编程语言逐渐发展成为一种告诉计算机该做什么的手段。然而，对于程序员来说，语言更恰当的定义是表达算法的一种手段。正如自然语言限制了阐述和论述一样，编程语言也限制了什么可以表达，什么不能轻易表达，并且对程序员的想法有着深刻而微妙的影响。Donald Knuth 建议将编程视为告诉另一个人你希望计算机做什么的艺术 [ Knu84 ]⁶。这个定义也许是最好的妥协。它承认概念清晰度和实现效率都是基本关注点。本书试图通过同时考虑其涉及的每个主题的概念和实现方面来体现这种妥协精神。

In the early days of computing the implementor's viewpoint was predominant. Programming languages evolved as a means of telling a computer what to do. For programmers, however, a language is more aptly defined as a means of expressing algorithms. Just as natural languages constrain exposition and discourse, so programming languages constrain what can and cannot easily be expressed, and have both profound and subtle influence over what the programmer can think. Donald Knuth has suggested that programming be regarded as the art of telling another human being what one wants the computer to do [Knu84].⁶ This definition perhaps strikes the best sort of compromise. It acknowledges that both conceptual clarity and implementation efficiency are fundamental concerns. This book attempts to capture this spirit of compromise, by simultaneously considering the conceptual and implementation aspects of each of the topics it covers.

1.2 编程语言范围

1.2 The Programming Language Spectrum

例 1.3

Example 1.3

编程语言的分类

Classification of programming languages

现有的许多语言可以根据其计算模型分为不同的类别。图 1.1显示了一组常见的类别。顶级划分区分了声明性语言和命令性语言，声明性语言的重点是计算机要做什么，命令性语言的重点是计算机应该如何做。■

The many existing languages can be classified into families based on their model of computation. Figure 1.1 shows a common set of families. The top-level division distinguishes between the declarative languages, in which the focus is on what the computer is to do, and the imperative languages, in which the focus is on how the computer should do it.■

声明式语言在某种意义上是“更高级的”；它们更符合程序员的观点，而不太符合实现者的观点。然而，命令式语言占主导地位，主要是出于性能原因。在声明式语言的设计中，存在着一种矛盾，一方面希望摆脱“不相关的”实现细节，另一方面又需要足够接近细节以至少控制算法的轮廓。毕竟，高效算法的设计是计算机科学的大部分内容。目前尚不清楚在多大程度上以及在哪些问题领域中，我们可以期望编译器为非常高抽象层次上陈述的问题找到好的算法。在编译器无法找到好算法的任何领域中，程序员都需要能够明确指定一个算法。

Declarative languages are in some sense “higher level”; they are more in tune with the programmer's point of view, and less with the implementor's point of view. Imperative languages predominate, however, mainly for performance reasons. There is a tension in the design of declarative languages between the desire to get away from “irrelevant” implementation details and the need to remain close enough to the details to at least control the outline of an algorithm. The design of efficient algorithms, after all, is what much of computer science is about. It is not yet clear to what extent, and in what problem domains, we can expect compilers to discover good algorithms for problems stated at a very high level of abstraction. In any domain in which the compiler cannot find a good algorithm, the programmer needs to be able to specify one explicitly.

在声明式和命令式语法家族中，有几个重要的子家族：

Within the declarative and imperative families, there are several important subfamilies:

■ 函数式语言采用基于函数递归定义的计算模型。它们的灵感来自lambda 演算，这是 Alonzo Church 在 20 世纪 30 年代开发的一种正式计算模型。本质上，程序被视为从输入到输出的函数，通过细化过程以更简单的函数来定义。此类别的语言包括 Lisp、ML 和 Haskell。

■ Functional languages employ a computational model based on the recursive definition of functions. They take their inspiration from the lambda calculus, a formal computational model developed by Alonzo Church in the 1930s. In essence, a program is considered a function from inputs to outputs, defined in terms of simpler functions through a process of refinement. Languages in this category include Lisp, ML, and Haskell.

■ 数据流语言将计算建模为原始功能节点之间的信息流（令牌） 。它们提供了一种固有的并行模型：节点由输入令牌的到达触发，并且可以并发操作。Id 和 Val 是数据流语言的示例。Sisal 是 Val 的后代，通常被描述为一种函数式语言。

■ Dataflow languages model computation as the flow of information (tokens) among primitive functional nodes. They provide an inherently parallel model: nodes are triggered by the arrival of input tokens, and can operate concurrently. Id and Val are examples of dataflow languages. Sisal, a descendant of Val, is more often described as a functional language.

■ 逻辑或基于约束的语言从谓词逻辑中汲取灵感。它们将计算建模为尝试查找满足某些指定关系的值，使用目标导向搜索通过一系列逻辑规则。Prolog 是最著名的逻辑语言。该术语有时也适用于 SQL 数据库语言、XSLT 脚本语言以及电子表格（如 Excel 及其前身）的可编程方面。

■ Logic or constraint-based languages take their inspiration from predicate logic. They model computation as an attempt to find values that satisfy certain specified relationships, using goal-directed search through a list of logical rules. Prolog is the best-known logic language. The term is also sometimes applied to the SQL database language, the XSLT scripting language, and programmable aspects of spreadsheets such as Excel and its predecessors.

■ 冯·诺依曼语言可能是最常见和应用最广泛的语言。它们包括 Fortran、Ada、C 以及所有其他以修改变量为基本计算手段的语言。7^函数式语言基于具有值的表达式，而冯·诺依曼语言则基于语句（尤其是赋值语句），这些语句通过改变内存值的副作用来影响后续计算。

■ The von Neumann languages are probably the most familiar and widely used. They include Fortran, Ada, C, and all of the others in which the basic means of computation is the modification of variables.⁷ Whereas functional languages are based on expressions that have values, von Neumann languages are based on statements (assignments in particular) that influence subsequent computation via the side effect of changing the value of memory.

■ 面向对象语言的根源可以追溯到 Simula 67。大多数面向对象语言与冯·诺依曼语言密切相关，但具有更结构化和分布式的内存和计算模型。面向对象语言不是将计算描绘成单片处理器对单片内存的操作，而是将其描绘成半独立对象之间的交互，每个对象都有自己的内部状态和用于管理该状态的子例程。Smalltalk 是最纯粹的面向对象语言；C++ 和 Java 可能是使用最广泛的语言。也可以设计面向对象的函数式语言（其中最著名的是 CLOS [ Kee89 ] 和 OCaml），但它们往往具有强烈的命令式风格。

■ Object-oriented languages trace their roots to Simula 67. Most are closely related to the von Neumann languages, but have a much more structured and distributed model of both memory and computation. Rather than picture computation as the operation of a monolithic processor on a monolithic memory, object-oriented languages picture it as interactions among semi-independent objects, each of which has both its own internal state and subroutines to manage that state. Smalltalk is the purest of the object-oriented languages; C++ and Java are probably the most widely used. It is also possible to devise object-oriented functional languages (the best known of these are CLOS [Kee89] and OCaml), but they tend to have a strong imperative flavor.

■ 脚本语言的特点是，它们强调协调或“粘合”来自周围环境的组件。一些脚本语言最初是为特定目的而开发的：csh和bash是作业控制 (shell) 程序的输入语言；PHP 和 JavaScript 主要用于生成动态 Web 内容；Lua 被广泛用于控制计算机游戏。其他语言，包括 Perl、Python 和 Ruby，则更注重通用性。大多数语言都强调快速原型设计，更注重表达的简易性而不是执行速度。

■ Scripting languages are distinguished by their emphasis on coordinating or “gluing together” components drawn from some surrounding context. Several scripting languages were originally developed for specific purposes: csh and bash are the input languages of job control (shell) programs; PHP and JavaScript are primarily intended for the generation of dynamic web content; Lua is widely used to control computer games. Other languages, including Perl, Python, and Ruby, are more deliberately general purpose. Most place an emphasis on rapid prototyping, with a bias toward ease of expression over speed of execution.

有人可能会认为并发（并行）语言应该形成一个单独的家族（本书确实用一章来介绍此类语言），但并发和顺序执行之间的区别与上述分类基本无关。目前，大多数并发程序都是使用特殊库包或编译器结合 Fortran 或 C 等顺序语言编写的。一些广泛使用的语言（包括 Java、C# 和 Ada）具有明确的并发特性。研究人员正在研究此处提到的每个语言家族中的并发性。

One might suspect that concurrent (parallel) languages would form a separate family (and indeed this book devotes a chapter to such languages), but the distinction between concurrent and sequential execution is mostly independent of the classifications above. Most concurrent programs are currently written using special library packages or compilers in conjunction with a sequential language such as Fortran or C. A few widely used languages, including Java, C#, and Ada, have explicitly concurrent features. Researchers are investigating concurrency in each of the language families mentioned here.

例 1.4

Example 1.4

C 语言中的 GCD 函数

GCD function in C

作为语言家族对比的一个简单示例，请考虑本章开头介绍的最大公约数 (GCD) 问题。对于这个问题，选择冯·诺依曼、函数式或逻辑编程不仅会影响代码的外观，还会影响程序员的思维方式。冯·诺依曼算法版本的算法非常重要：

As a simple example of the contrast among language families, consider the greatest common divisor (GCD) problem introduced at the beginning of this chapter. The choice among, say, von Neumann, functional, or logic programming for this problem influences not only the appearance of the code, but how the programmer thinks. The von Neumann algorithm version of the algorithm is very imperative:

要计算a和b的gcd，请检查a和b是否相等。如果相等，则打印其中一个并停止。否则，用它们的差值替换较大的一个并重复。

To compute the gcd of a and b, check to see if a and b are equal. If so, print one of them and stop. Otherwise, replace the larger one by their difference and repeat.

该算法的 C 代码如图1.2所示。■

C code for this algorithm appears at the top of Figure 1.2. ■

需要强调的是，语言家族之间的区别并不明显。例如，冯·诺依曼语言和面向对象语言之间的区别通常非常模糊，而且许多脚本语言也是面向对象的。大多数函数式和逻辑语言都包含一些命令式特性，而最近几种命令式语言也增加了函数式特性。上述描述旨在捕捉各家族的一般特征，而不是提供正式定义。

It should be emphasized that the distinctions among language families are not clear-cut. The division between the von Neumann and object-oriented languages, for example, is often very fuzzy, and many scripting languages are also object-oriented. Most of the functional and logic languages include some imperative features, and several recent imperative languages have added functional features. The descriptions above are meant to capture the general flavor of the families, without providing formal definitions.

本书主要关注命令式语言（冯·诺依曼语言和面向对象语言）。然而，许多问题都跨越了不同的范畴，感兴趣的读者会发现本书大多数章节中都有很多适用于替代计算模型的内容。第11 章至第 14章包含有关函数式、逻辑、并发和脚本语言的附加材料。

Imperative languages—von Neumann and object-oriented—receive the bulk of the attention in this book. Many issues cut across family lines, however, and the interested reader will discover much that is applicable to alternative computational models in most chapters of the book. Chapters 11 through 14 contain additional material on functional, logic, concurrent, and scripting languages.

1.3 为什么要学习编程语言？

1.3 Why Study Programming Languages?

编程语言是计算机科学和典型计算机科学课程的核心。与大多数车主一样，熟悉一种或多种高级语言的学生通常对学习其他语言以及了解“引擎盖下”发生的事情感到好奇。学习语言很有趣。它也很实用。

Programming languages are central to computer science, and to the typical computer science curriculum. Like most car owners, students who have become familiar with one or more high-level languages are generally curious to learn about other languages, and to know what is going on “under the hood.” Learning about languages is interesting. It's also practical.

首先，对语言设计和实现的良好理解可以帮助人们为任何给定的任务选择最合适的语言。大多数语言在某些方面比其他方面更胜一筹。很少有程序员会选择 Fortran 进行符号计算或字符串处理，但其他选择却远没有那么明确。对于系统编程，应该选择 C、C++ 还是 C#？对于科学计算，应该选择 Fortran 还是 C？对于基于 Web 的应用程序，应该选择 PHP 还是 Ruby？对于嵌入式系统，应该选择 Ada 还是 C？对于图形用户界面，应该选择 Visual Basic 还是 Java？本书应该可以帮助您做出这样的决定。

For one thing, a good understanding of language design and implementation can help one choose the most appropriate language for any given task. Most languages are better for some things than for others. Few programmers are likely to choose Fortran for symbolic computing or string processing, but other choices are not nearly so clear-cut. Should one choose C, C++, or C# for systems programming? Fortran or C for scientific computations? PHP or Ruby for a web-based application? Ada or C for embedded systems? Visual Basic or Java for a graphical user interface? This book should help equip you to make such decisions.

同样，本书应该使学习新语言变得更容易。许多语言是密切相关的。如果你已经了解 C++，那么 Java 和 C# 就更容易学习；如果你已经了解 Scheme，那么 Common Lisp 就更容易学习；如果你已经了解 ML，那么 Haskell 就更容易学习。更重要的是，所有编程语言都有一些基本概念。这些概念中的大多数都是本书各章的主题：类型、控制（迭代、选择、递归、非确定性、并发）、抽象和命名。用这些概念来思考，可以更容易地吸收新语言的语法（形式）和语义（含义），而不是凭空而来。这种情况类似于自然界中发生的情况语言：熟悉语法形式可以更轻松地学习外语。

Similarly, this book should make it easier to learn new languages. Many languages are closely related. Java and C# are easier to learn if you already know C++; Common Lisp if you already know Scheme; Haskell if you already know ML. More importantly, there are basic concepts that underlie all programming languages. Most of these concepts are the subject of chapters in this book: types, control (iteration, selection, recursion, nondeterminacy, concurrency), abstraction, and naming. Thinking in terms of these concepts makes it easier to assimilate the syntax (form) and semantics (meaning) of new languages, compared to picking them up in a vacuum. The situation is analogous to what happens in natural languages: a good knowledge of grammatical forms makes it easier to learn a foreign language.

无论您学习什么语言，了解其设计和实现中的决策都可以帮助您更好地使用它。本书应该可以帮助您：

Whatever language you learn, understanding the decisions that went into its design and implementation will help you use it better. This book should help you:

理解晦涩难懂的功能。典型的 C++ 程序员很少使用联合、多重继承、可变数量的参数或 .* 运算符。（如果您不知道这些是什么，请不要担心！）就像它简化了新语言的吸收一样，理解基本概念可以让您在手册中查找详细信息时更容易理解这些功能。

Understand obscure features. The typical C++ programmer rarely uses unions, multiple inheritance, variable numbers of arguments, or the .* operator. (If you don't know what these are, don't worry!) Just as it simplifies the assimilation of new languages, an understanding of basic concepts makes it easier to understand these features when you look up the details in the manual.

根据对实现成本的了解，选择表达事物的备选方法。例如，在 C++ 中，程序员可能需要避免不必要的临时变量，并尽可能使用复制构造函数，以尽量减少初始化成本。在 Java 中，他们可能希望使用Executor对象，而不是显式创建线程。对于某些（较差的）编译器，他们可能需要采用特殊的编程习惯用法来获得最快的代码：用于数组遍历的指针；x*x 而不是 x**2。在任何语言中，他们都需要能够评估抽象的备选实现之间的权衡——例如，对于位集基数等函数，在计算和表查找之间进行权衡，这些函数可以用任何一种方式实现。

Choose among alternative ways to express things, based on a knowledge of implementation costs. In C++, for example, programmers may need to avoid unnecessary temporary variables, and use copy constructors whenever possible, to minimize the cost of initialization. In Java they may wish to use Executor objects rather than explicit thread creation. With certain (poor) compilers, they may need to adopt special programming idioms to get the fastest code: pointers for array traversal; x*x instead of x**2. In any language, they need to be able to evaluate the tradeoffs among alternative implementations of abstractions—for example between computation and table lookup for functions like bit set cardinality, which can be implemented either way.

充分利用调试器、汇编器、链接器和相关工具。一般来说，高级语言程序员不需要为实现细节而烦恼。但有时，了解这些细节几乎是必不可少的。如果一个人愿意深入了解这些细节，那么顽固的错误或不寻常的系统构建问题可能会变得容易得多。

Make good use of debuggers, assemblers, linkers, and related tools. In general, the high-level language programmer should not need to bother with implementation details. There are times, however, when an understanding of those details is virtually essential. The tenacious bug or unusual system-building problem may be dramatically easier to handle if one is willing to peek at the bits.

模拟缺少有用功能的语言。某些非常有用的功能在较旧的语言中缺失，但可以通过遵循刻意的（如果不是强制的）编程风格来模拟。例如，在 Fortran 的较旧方言中，熟悉现代控制结构的程序员可以使用注释和自律来编写结构良好的代码。同样，在抽象功能较差的语言中，注释和命名约定可以帮助模仿模块化结构，并且可以使用子例程和静态变量来模仿Clu、C#、Python 和 Ruby 中极其有用的迭代器（我们将在第 6.5.3 节中学习）。

Simulate useful features in languages that lack them. Certain very useful features are missing in older languages, but can be emulated by following a deliberate (if unenforced) programming style. In older dialects of Fortran, for example, programmers familiar with modern control constructs can use comments and self-discipline to write well-structured code. Similarly, in languages with poor abstraction facilities, comments and naming conventions can help imitate modular structure, and the extremely useful iterators of Clu, C#, Python, and Ruby (which we will study in Section 6.5.3) can be imitated with subroutines and static variables.

无论语言技术出现在哪里，都要更好地利用它。大多数程序员永远不会设计或实现传统的编程语言，但大多数程序员需要语言技术来完成其他编程任务。典型的个人计算机包含数十种结构化格式的文件，包括文字处理、电子表格、演示文稿、光栅和矢量图形、音乐、视频、数据库以及各种其他应用领域。Web 内容越来越多地以 XML 表示，这是一种基于文本的格式，旨在通过 XSLT 脚本语言轻松操作（在C-14.3.5 节中讨论）。要解析、分析、生成、优化和其他操作的代码因此，几乎任何复杂的程序都可以找到操纵结构化数据的方法，所有这些代码都基于语言技术。掌握了这项技术的程序员将更有能力编写结构良好、可维护的工具。

Make better use of language technology wherever it appears. Most programmers will never design or implement a conventional programming language, but most will need language technology for other programming tasks. The typical personal computer contains files in dozens of structured formats, encompassing word processing, spreadsheets, presentations, raster and vector graphics, music, video, databases, and a wide variety of other application domains. Web content is increasingly represented in XML, a text-based format designed for easy manipulation in the XSLT scripting language (discussed in Section C-14.3.5). Code to parse, analyze, generate, optimize, and otherwise manipulate structured data can thus be found in almost any sophisticated program, and all of this code is based on language technology. Programmers with a strong grasp of this technology will be in a better position to write well-structured, maintainable tools.

类似地，大多数工具本身可以通过启动配置文件、命令行参数、输入命令或内置扩展语言（将在第 14 章中详细讨论）进行定制。我的主目录中有 250 多个单独的配置（“首选项”）文件。我个人的emacs文本编辑器配置文件包含 1200 多行 Lisp 代码。如今，几乎任何复杂程序的用户都需要充分利用配置或扩展语言。这种程序的设计者要么需要采用（并调整）某些现有的扩展语言，要么发明自己的新符号。精通语言理论的程序员将能够更好地设计出优雅、结构良好的符号，以满足当前用户的需求并促进未来的开发。

In a similar vein, most tools themselves can be customized, via start-up configuration files, command-line arguments, input commands, or built-in extension languages (considered in more detail in Chapter 14). My home directory holds more than 250 separate configuration (“preference”) files. My personal configuration files for the emacs text editor comprise more than 1200 lines of Lisp code. The user of almost any sophisticated program today will need to make good use of configuration or extension languages. The designers of such a program will need either to adopt (and adapt) some existing extension language, or to invent new notation of their own. Programmers with a strong grasp of language theory will be in a better position to design elegant, well-structured notation that meets the needs of current users and facilitates future development.

最后，如果您愿意，本书应该可以帮助您为进一步研究语言设计或实现做好准备。如果您对这些领域感兴趣，它还将帮助您理解语言与操作系统和体系结构之间的交互。

Finally, this book should help prepare you for further study in language design or implementation, should you be so inclined. It will also equip you to understand the interactions of languages with operating systems and architectures, should those areas draw your interest.

1.4 编译和解释

1.4 Compilation and Interpretation

例 1.7

Example 1.7

纯编译

Pure compilation

在最高的抽象层次上，高级语言中程序的编译和执行看起来是这样的：

At the highest level of abstraction, the compilation and execution of a program in a high-level language look something like this:

编译器将高级源程序翻译成等效的目标程序（通常是机器语言），然后就消失了。在稍后的某个时间，用户告诉操作系统运行目标程序。编译器是编译期间的控制点；目标程序是其自身执行期间的控制点。编译器本身是一个机器语言程序，大概是通过编译其他高级程序创建的。当以操作系统理解的格式写入文件时，机器语言通常称为目标代码。■

The compiler translates the high-level source program into an equivalent target program (typically in machine language), and then goes away. At some arbitrary later time, the user tells the operating system to run the target program. The compiler is the locus of control during compilation; the target program is the locus of control during its own execution. The compiler is itself a machine language program, presumably created by compiling some other high-level program. When written to a file in a format understood by the operating system, machine language is commonly known as object code. ■

例 1.8

Example 1.8

纯粹的解释

Pure interpretation

高级语言的另一种实现方式称为解释：

An alternative style of implementation for high-level languages is known as interpretation:

与编译器不同，解释器在应用程序执行期间一直存在。事实上，解释器是执行期间的控制中心。实际上，解释器实现了一个虚拟机，其“机器语言”是高级编程语言。解释器一次或多或少读取该语言的语句，并在执行过程中执行它们。■

Unlike a compiler, an interpreter stays around for the execution of the application. In fact, the interpreter is the locus of control during that execution. In effect, the interpreter implements a virtual machine whose “machine language” is the high-level programming language. The interpreter reads statements in that language more or less one at a time, executing them as it goes along. ■

一般而言，解释比编译具有更大的灵活性和更好的诊断（错误消息）。由于直接执行源代码，解释器可以包含出色的源代码级调试器。它还可以处理那些程序基本特性（例如变量的大小和类型，甚至哪些名称引用哪些变量）取决于输入数据的语言。某些语言特性几乎不可能在没有解释的情况下实现：例如，在 Lisp 和 Prolog 中，程序可以编写自己的新片段并动态执行它们。（几种脚本语言也提供此功能。）将程序实现的决策推迟到运行时称为后期绑定；我们将在第 3.1 节中详细讨论它。

In general, interpretation leads to greater flexibility and better diagnostics (error messages) than does compilation. Because the source code is being executed directly, the interpreter can include an excellent source-level debugger. It can also cope with languages in which fundamental characteristics of the program, such as the sizes and types of variables, or even which names refer to which variables, can depend on the input data. Some language features are almost impossible to implement without interpretation: in Lisp and Prolog, for example, a program can write new pieces of itself and execute them on the fly. (Several scripting languages also provide this capability.) Delaying decisions about program implementation until run time is known as late binding; we will discuss it at greater length in Section 3.1.

相比之下，编译通常会带来更好的性能。通常，编译时做出的决定是运行时不需要做出的决定。例如，如果编译器可以保证变量x始终位于位置49378，它就可以生成机器语言指令，以便在源程序引用x时访问此位置。相比之下，解释器可能需要在每次访问x时在表中查找它，以找到它的位置。由于程序（的最终版本）仅编译一次，但通常执行多次，因此节省的成本可能非常可观，特别是如果解释器在循环的每次迭代中都做不必要的工作。

Compilation, by contrast, generally leads to better performance. In general, a decision made at compile time is a decision that does not need to be made at run time. For example, if the compiler can guarantee that variable x will always lie at location 49378, it can generate machine language instructions that access this location whenever the source program refers to x. By contrast, an interpreter may need to look x up in a table every time it is accessed, in order to find its location. Since the (final version of a) program is compiled only once, but generally executed many times, the savings can be substantial, particularly if the interpreter is doing unnecessary work in every iteration of a loop.

例 1.9

Example 1.9

混合编译和解释

Mixing compilation and interpretation

虽然编译和解释之间的概念差异很明显，但大多数语言实现都包含两者的混合。它们通常看起来像这样：

While the conceptual difference between compilation and interpretation is clear, most language implementations include a mixture of both. They typically look like this:

如果初始翻译器很简单，我们通常说一种语言是“解释型”的。如果翻译器很复杂，我们说这种语言是“编译型”的。这种区别可能令人困惑，因为“简单”和“复杂”是主观术语，并且编译器（复杂翻译器）可以生成代码，然后由复杂的虚拟机（解释器）执行；事实上，这正是 Java 中默认发生的情况。如果翻译器彻底分析了语言（而不是进行某种“机械”转换），并且中间程序与源程序没有太大相似之处，我们仍然说这种语言是编译型的。这两个特征——彻底的分析和非平凡的转换——是编译的标志。■

We generally say that a language is “interpreted” when the initial translator is simple. If the translator is complicated, we say that the language is “compiled.” The distinction can be confusing because “simple” and “complicated” are subjective terms, and because it is possible for a compiler (complicated translator) to produce code that is then executed by a complicated virtual machine (interpreter); this is in fact precisely what happens by default in Java. We still say that a language is compiled if the translator analyzes it thoroughly (rather than effecting some “mechanical” transformation), and if the intermediate program does not bear a strong resemblance to the source. These two characteristics—thorough analysis and nontrivial transformation—are the hallmarks of compilation. ■

在实践中，我们看到了广泛的实现策略：

In practice one sees a broad spectrum of implementation strategies:

在 Basic 的一些早期实现中，手册实际上建议从程序中删除注释以提高其性能。这些实现是纯粹的解释器；它们每次执行程序的给定部分时都会重新读取（然后忽略）注释。它们没有初始翻译器。

In some very early implementations of Basic, the manual actually suggested removing comments from a program in order to improve its performance. These implementations were pure interpreters; they would re-read (and then ignore) the comments every time they executed a given part of the program. They had no initial translator.

例 1.11

Example 1.11

库例程和链接

Library routines and linking

■ 典型的 Fortran 实现接近于纯编译。编译器将 Fortran 源代码翻译成机器语言。但是，它通常依赖于不属于原始程序的子例程库的存在。示例包括数学函数（ sin、cos、log等）和 I/O。编译器依赖于一个单独的程序（称为链接器）将适当的库例程合并到最终程序中：

■ The typical Fortran implementation comes close to pure compilation. The compiler translates Fortran source into machine language. Usually, however, it counts on the existence of a library of subroutines that are not part of the original program. Examples include mathematical functions (sin, cos, log, etc.) and I/O. The compiler relies on a separate program, known as a linker, to merge the appropriate library routines into the final program:

从某种意义上说，人们可以将库例程视为硬件指令集的扩展。然后，可以将编译器视为为虚拟机生成代码，该代码同时包含硬件和库的功能。

In some sense, one may think of the library routines as extensions to the hardware instruction set. The compiler can then be thought of as generating code for a virtual machine that includes the capabilities of both the hardware and the library.

从更字面意义上讲，可以在 Fortran 例程中找到格式化输出的解释。Fortran 允许使用格式语句来控制输出在列中的对齐方式、浮点数的有效位数和科学计数法类型、前导零的包含/隐藏等等。程序可以动态计算自己的格式。输出库例程包括一个格式解释器。在C 及其后代的printf例程中可以找到类似的解释器。■

In a more literal sense, one can find interpretation in the Fortran routines for formatted output. Fortran permits the use of format statements that control the alignment of output in columns, the number of significant digits and type of scientific notation for floating-point numbers, inclusion/suppression of leading zeros, and so on. Programs can compute their own formats on the fly. The output library routines include a format interpreter. A similar interpreter can be found in the printf routine of C and its descendants. ■

例 1.12

Example 1.12

编译后汇编

Post-compilation assembly

■ 许多编译器生成汇编语言而不是机器语言。这种约定有利于调试，因为汇编语言更易于人们阅读，并且使编译器不受操作系统新版本可能要求的机器语言文件格式更改的影响（只有汇编程序必须更改，许多编译器都共享它）：

■ Many compilers generate assembly language instead of machine language. This convention facilitates debugging, since assembly language is easier for people to read, and isolates the compiler from changes in the format of machine language files that may be mandated by new releases of the operating system (only the assembler must be changed, and it is shared by many compilers):

■

■

例 1.13

Example 1.13

C 预处理器

The C preprocessor

C 语言（以及在 Unix 下运行的许多其他语言）的编译器都以预处理器开始，该预处理器可删除注释并扩展宏。预处理器还可以被指示删除代码本身的某些部分，从而提供条件编译功能，允许从同一源构建程序的多个版本：

Compilers for C (and for many other languages running under Unix) begin with a preprocessor that removes comments and expands macros. The preprocessor can also be instructed to delete portions of the code itself, providing a conditional compilation facility that allows several versions of a program to be built from the same source:

■

■

例 1.14

Example 1.14

源到源翻译

Source-to-source translation

■ 数量惊人的编译器会以某种高级语言生成输出 — 通常是 C 语言或输入语言的某种简化版本。这种源到源的翻译在研究语言和语言开发的早期阶段尤为常见。一个著名的例子是 AT&T 最初的 C++ 编译器。这确实是一个真正的编译器，尽管它生成的是 C 而不是汇编程序：它对 C++ 源程序的语法和语义进行了完整的分析，除了极少数例外生成了程序员在运行程序之前会看到的所有错误消息。事实上，程序员通常不知道 C 编译器在后台运行。C++ 编译器不会调用 C 编译器，除非它生成的 C 代码能够通过第二轮编译而不会产生任何错误消息：

■ A surprising number of compilers generate output in some high-level language—commonly C or some simplified version of the input language. Such source-to-source translation is particularly common in research languages and during the early stages of language development. One famous example was AT&T's original compiler for C++. This was indeed a true compiler, though it generated C instead of assembler: it performed a complete analysis of the syntax and semantics of the C++ source program, and with very few exceptions generated all of the error messages that a programmer would see prior to running the program. In fact, programmers were generally unaware that the C compiler was being used behind the scenes. The C++ compiler did not invoke the C compiler unless it had generated C code that would pass through the second round of compilation without producing any error messages:

■

■

有时，人们会听到 C++ 编译器被称为预处理器，大概是因为它生成的高级输出会被编译。我认为这是对术语的误用：编译器试图“理解”其源代码；而预处理器则不会。预处理器根据简单的模式匹配执行转换，并且可能会生成输出，这些输出在后续转换阶段运行时会生成错误消息。

Occasionally one would hear the C++ compiler referred to as a preprocessor, presumably because it generated high-level output that was in turn compiled. I consider this a misuse of the term: compilers attempt to “understand” their source; preprocessors do not. Preprocessors perform transformations based on simple pattern matching, and may well produce output that will generate error messages when run through a subsequent stage of translation.

例 1.15

Example 1.15

引导

Bootstrapping

■ 许多编译器都是自托管的：它们用编译的语言编写 — Ada 编译器用 Ada 编写，C 编译器用 C 编写。这引出了一个显而易见的问题：首先如何编译编译器？答案是使用一种称为bootstrapping的技术，这个术语源于一个故意荒谬的概念，即通过拉动引导装置将自己抬离地面。简而言之，从一个简单的实现（通常是解释器）开始，并使用它来构建逐渐更复杂的版本。我们可以用一个历史例子来说明这个想法。

■ Many compilers are self-hosting: they are written in the language they compile—Ada compilers in Ada, C compilers in C. This raises an obvious question: how does one compile the compiler in the first place? The answer is to use a technique known as bootstrapping, a term derived from the intentionally ridiculous notion of lifting oneself off the ground by pulling on one's bootstraps. In a nutshell, one starts with a simple implementation—often an interpreter—and uses it to build progressively more sophisticated versions. We can illustrate the idea with an historical example.

许多早期的 Pascal 编译器都是围绕 Niklaus Wirth 分发的一组工具构建的。其中包括：

Many early Pascal compilers were built around a set of tools distributed by Niklaus Wirth. These included the following:

– 用 Pascal 编写的 Pascal 编译器，可以生成P 代码输出，P 代码是一种基于堆栈的语言，类似于现代 Java 编译器的字节码

– A Pascal compiler, written in Pascal, that would generate output in P-code, a stack-based language similar to the bytecode of modern Java compilers

– 同一个编译器，已经翻译成 P 代码

– The same compiler, already translated into P-code

– 用 Pascal 编写的 P 代码解释器

– A P-code interpreter, written in Pascal

要在本地机器上启动并运行 Pascal，该工具集的用户只需将 P 代码解释器（手动）翻译成某种本地可用的语言。这种翻译并不困难；解释器很小。通过在 P 代码上运行编译器的 P 代码版本解释器，然后可以将任意 Pascal 程序编译为 P 代码，然后可以在解释器上运行。为了获得更快的实现，可以修改 Pascal 编译器的 Pascal 版本以生成本地可用的汇编语言或机器语言，而不是生成 P 代码（这是一项稍微困难的任务）。然后可以引导此编译器（通过自身运行）以生成编译器的机器代码版本：

To get Pascal up and running on a local machine, the user of the tool set needed only to translate the P-code interpreter (by hand) into some locally available language. This translation was not a difficult task; the interpreter was small. By running the P-code version of the compiler on top of the P-code interpreter, one could then compile arbitrary Pascal programs into P-code, which could in turn be run on the interpreter. To get a faster implementation, one could modify the Pascal version of the Pascal compiler to generate a locally available variety of assembly or machine language, instead of generating P-code (a somewhat more difficult task). This compiler could then be bootstrapped—run through itself—to yield a machine-code version of the compiler:

在更一般的背景下，假设我们正在为一种新的编程语言构建第一个编译器。假设我们的目标系统上有一个 C 编译器，我们可能会先用 C 的简单子集编写一个编译器，用于我们新编程语言的一个同样简单的子集。一旦这个编译器开始工作，我们就可以手动将 C 代码翻译成我们新语言的（子集），然后通过编译器本身运行新的源代码。之后，我们可以反复扩展编译器以接受更大的子集新的编程语言，再次引导它，并使用扩展语言来实现更大的子集。这种“自托管”实现实际上相当常见。■

In a more general context, suppose we were building one of the first compilers for a new programming language. Assuming we have a C compiler on our target system, we might start by writing, in a simple subset of C, a compiler for an equally simple subset of our new programming language. Once this compiler was working, we could hand-translate the C code into (the subset of) our new language, and then run the new source through the compiler itself. After that, we could repeatedly extend the compiler to accept a larger subset of the new programming language, bootstrap it again, and use the extended language to implement an even larger subset. “Self-hosting” implementations of this sort are actually quite common. ■

例 1.17

Example 1.17

动态和即时编译

Dynamic and just-in-time compilation

■ 在某些情况下，编程系统可能会故意将编译延迟到最后一刻。一个例子出现在语言实现（例如，Lisp 或 Prolog）中，这些实现会动态调用编译器，将新创建的源代码转换为机器语言，或针对特定输入集优化代码。另一个例子出现在 Java 实现中。Java 语言定义定义了一种与机器无关的中间形式，称为 Java字节码。字节码是 Java 程序分发的标准格式；它允许程序通过互联网轻松传输，然后在任何平台上运行。第一个 Java 实现基于字节码解释器，但现代实现使用即时编译器获得了明显更好的性能，该编译器在每次执行程序之前立即将字节码转换为机器语言：

■ In some cases a programming system may deliberately delay compilation until the last possible moment. One example occurs in language implementations (e.g., for Lisp or Prolog) that invoke the compiler on the fly, to translate newly created source into machine language, or to optimize the code for a particular input set. Another example occurs in implementations of Java. The Java language definition defines a machine-independent intermediate form known as Java bytecode. Bytecode is the standard format for distribution of Java programs; it allows programs to be transferred easily over the Internet, and then run on any platform. The first Java implementations were based on byte-code interpreters, but modern implementations obtain significantly better performance with a just-in-time compiler that translates bytecode into machine language immediately before each execution of the program:

同样，C# 也用于即时翻译。主 C# 编译器生成通用中间语言(CIL)，然后在执行之前立即将其翻译成机器语言。CIL 刻意与语言无关，因此可以用于由各种前端编译器生成的代码。我们将在第 16.1 节详细探讨 Java 和 C# 实现。■

C#, similarly, is intended for just-in-time translation. The main C# compiler produces Common Intermediate Language (CIL), which is then translated into machine language immediately prior to execution. CIL is deliberately language independent, so it can be used for code produced by a variety of front-end compilers. We will explore the Java and C# implementations in detail in Section 16.1. ■

正如这些例子中所表明的，编译器不一定会将高级编程语言翻译成机器语言。事实上，有些编译器接受的输入我们可能根本不会立即认为是程序。例如，像 T _E X 这样的文本格式化程序会将高级文档描述编译成激光打印机或照排机的命令。（许多激光打印机本身包含预安装的 Postscript 页面描述语言解释器。）数据库系统的查询语言处理器会将 SQL 等语言翻译成对文件的原始操作。甚至还有编译器将逻辑级电路规范翻译成计算机芯片的照相掩模版。虽然本书的重点是命令式编程语言，但“编译”一词适用于当我们在充分分析输入含义的情况下从一种非平凡语言自动翻译成另一种语言时。

As some of these examples make clear, a compiler does not necessarily translate from a high-level programming language into machine language. Some compilers, in fact, accept inputs that we might not immediately think of as programs at all. Text formatters like T_EX, for example, compile high-level document descriptions into commands for a laser printer or phototypesetter. (Many laser printers themselves contain pre-installed interpreters for the Postscript page-description language.) Query language processors for database systems translate languages like SQL into primitive operations on files. There are even compilers that translate logic-level circuit specifications into photographic masks for computer chips. Though the focus in this book is on imperative programming languages, the term “compilation” applies whenever we translate automatically from one nontrivial language to another, with full analysis of the meaning of the input.

1.5 编程环境

1.5 Programming Environments

编译器和解释器并不是孤立存在的。程序员可以通过许多其他工具来协助他们的工作。前面提到了汇编器、调试器、预处理器和链接器。每个程序员都熟悉编辑器。它们可能配备了交叉引用功能，使程序员能够在给定对象使用点的情况下找到定义该对象的点。漂亮的打印机有助于强制执行格式约定。样式检查器强制执行的句法或语义约定可能比编译器强制执行的约定更严格（参见探索 1.14）。配置管理工具有助于跟踪大型软件系统中单独编译的模块（的许多版本）之间的依赖关系。阅读工具不仅适用于文本，也适用于可能以二进制形式存储的中间语言。分析器和其他性能分析工具通常与调试器协同工作，以帮助识别程序中消耗大量计算时间的部分。

Compilers and interpreters do not exist in isolation. Programmers are assisted in their work by a host of other tools. Assemblers, debuggers, preprocessors, and linkers were mentioned earlier. Editors are familiar to every programmer. They may be augmented with cross-referencing facilities that allow the programmer to find the point at which an object is defined, given a point at which it is used. Pretty printers help enforce formatting conventions. Style checkers enforce syntactic or semantic conventions that may be tighter than those enforced by the compiler (see Exploration 1.14). Configuration management tools help keep track of dependences among the (many versions of) separately compiled modules in a large software system. Perusal tools exist not only for text but also for intermediate languages that may be stored in binary. Profilers and other performance analysis tools often work in conjunction with debuggers to help identify the pieces of a program that consume the bulk of its computation time.

在较旧的编程环境中，工具可能会根据用户的明确请求单独执行。例如，如果正在运行的程序因“总线错误”（无效地址）消息而异常终止，则用户可以选择调用调试器来检查操作系统转储的“核心”文件。然后，他或她可能会尝试通过设置断点、启用跟踪等来识别程序错误，并在调试器的控制下再次运行该程序。一旦发现错误，用户将调用编辑器进行适当的更改。然后，他或她将重新编译修改后的程序，可能借助配置管理器。

In older programming environments, tools may be executed individually, at the explicit request of the user. If a running program terminates abnormally with a “bus error” (invalid address) message, for example, the user may choose to invoke a debugger to examine the “core” file dumped by the operating system. He or she may then attempt to identify the program bug by setting breakpoints, enabling tracing and so on, and running the program again under the control of the debugger. Once the bug is found, the user will invoke the editor to make an appropriate change. He or she will then recompile the modified program, possibly with the help of a configuration manager.

现代环境提供了更多集成工具。当集成开发环境 (IDE) 中出现无效地址错误时，用户的屏幕上可能会出现一个新窗口，其中突出显示发生错误的源代码行。然后可以在此窗口中设置断点和跟踪，而无需明确调用调试器。无需明确调用编辑器即可对源代码进行更改。如果用户在进行更改后要求重新运行程序，则可以构建新版本，而无需明确调用编译器或配置管理器。

Modern environments provide more integrated tools. When an invalid address error occurs in an integrated development environment (IDE), a new window is likely to appear on the user's screen, with the line of source code at which the error occurred highlighted. Breakpoints and tracing can then be set in this window without explicitly invoking a debugger. Changes to the source can be made without explicitly invoking an editor. If the user asks to rerun the program after making changes, a new version may be built without explicitly invoking the compiler or configuration manager.

IDE 的编辑器可能包含语言语法知识，为所有标准控制结构提供模板，并在输入时检查语法。在内部，IDE 可能不仅维护程序的源代码和目标代码，还维护部分编译的内部表示。编辑源代码时，内部表示将自动更新 - 通常是增量更新（无需重新解析源代码的大部分内容）。在某些情况下，对程序的结构更改可能首先在内部表示中实现，然后自动反映在源代码中。

The editor for an IDE may incorporate knowledge of language syntax, providing templates for all the standard control structures, and checking syntax as it is typed in. Internally, the IDE is likely to maintain not only a program's source and object code, but also a partially compiled internal representation. When the source is edited, the internal representation will be updated automatically—often incrementally (without reparsing large portions of the source). In some cases, structural changes to the program may be implemented first in the internal representation, and then automatically reflected in the source.

IDE 是 Smalltalk 的基础——几乎不可能将该语言与其图形环境分开——自 20 世纪 80 年代以来，它一直被常规用于 Common Lisp。随着图形界面的普及，集成环境已在很大程度上取代了许多语言和系统的命令行工具。流行的开源 IDE 包括 Eclipse 和 NetBeans。商业系统包括 Microsoft 的 Visual Studio 环境和 Apple 的 XCode 环境。集成的大部分外观也可以在复杂的编辑器（如emacs ）中实现。

IDEs are fundamental to Smalltalk—it is nearly impossible to separate the language from its graphical environment—and have been routinely used for Common Lisp since the 1980s. With the ubiquity of graphical interfaces, integrated environments have largely displaced command-line tools for many languages and systems. Popular open-source IDEs include Eclipse and NetBeans. Commercial systems include the Visual Studio environment from Microsoft and the XCode environment from Apple. Much of the appearance of integration can also be achieved within sophisticated editors such as emacs.

1.6 编译概述

1.6 An Overview of Compilation

编译器是研究最深入的计算机程序之一。我们将在本书的其余部分，尤其是第 2 章、第 4 章、第 15 章和第17章中反复讨论它们。本节的其余部分提供了介绍性概述。

Compilers are among the most well-studied computer programs. We will consider them repeatedly throughout the rest of the book, and in chapters 2, 4, 15, and 17 in particular. The remainder of this section provides an introductory overview.

例 1.19

Example 1.19

编译和解释阶段

Phases of compilation and interpretation

在典型的编译器中，编译过程会经历一系列明确定义的阶段，如图1.3所示。每个阶段都会发现对后续阶段有用的信息，或者将程序转换为对后续阶段更有用的形式。

In a typical compiler, compilation proceeds through a series of well-defined phases, shown in Figure 1.3. Each phase discovers information of use to later phases, or transforms the program into a form that is more useful to the subsequent phase.

前几个阶段（直到语义分析）用于弄清楚源程序的含义。它们有时被称为编译器的前端。最后几个阶段用于构建等效的目标程序。它们有时被称为编译器的后端。

The first few phases (up through semantic analysis) serve to figure out the meaning of the source program. They are sometimes called the front end of the compiler. The last few phases serve to construct an equivalent target program. They are sometimes called the back end of the compiler.

解释器（图 1.4）与编译器共享前端结构，但直接“执行”（解释）中间形式，而不是将其翻译成机器语言。执行通常采用一组相互递归的子例程的形式，这些子例程遍历（“遍历”）语法树，按程序顺序“执行”其节点。许多编译器和解释器阶段可以根据源语言和/或目标语言的正式描述自动创建。■

An interpreter (Figure 1.4) shares the compiler's front-end structure, but “executes” (interprets) the intermediate form directly, rather than translating it into machine language. The execution typically takes the form of a set of mutually recursive subroutines that traverse (“walk”) the syntax tree, “executing” its nodes in program order. Many compiler and interpreter phases can be created automatically from a formal description of the source and/or target languages. ■

有时我们会听到有人将编译描述为一系列过程。过程是一个阶段或一组阶段，它们相对于编译的其余部分是序列化的：它在前面的阶段完成后才开始，并在任何后续阶段开始之前完成。如果需要，可以将过程编写为单独的程序，从文件读取其输入并将其输出写入文件。编译器通常分为几个过程，以便前端可以由多种机器（目标语言）的编译器共享，并且后端可以由多种源语言的编译器共享。在某些实现中，前端和后端可以由负责独立于语言和机器的代码改进的“中间端”分隔开。先前由于 20 世纪 80 年代中后期内存容量的急剧增加，编译器有时也被分为几个过程来尽量减少内存使用：每完成一个过程，下一个过程就可以重用其代码空间。

One will sometimes hear compilation described as a series of passes. A pass is a phase or set of phases that is serialized with respect to the rest of compilation: it does not start until previous phases have completed, and it finishes before any subsequent phases start. If desired, a pass may be written as a separate program, reading its input from a file and writing its output to a file. Compilers are commonly divided into passes so that the front end may be shared by compilers for more than one machine (target language), and so that the back end may be shared by compilers for more than one source language. In some implementations the front end and the back end may be separated by a “middle end” that is responsible for language- and machine-independent code improvement. Prior to the dramatic increases in memory sizes of the mid to late 1980s, compilers were also sometimes divided into passes to minimize memory usage: as each pass completed, the next could reuse its code space.

1.6.1 词汇和语法分析

1.6.1 Lexical and Syntax Analysis

例 1.20

Example 1.20

C 语言中的 GCD 程序

GCD program in C

考虑本章开头介绍的最大公约数 (GCD) 问题，如图1.2所示。假设一些简单的 I/O 例程，并将该函数重铸为一个独立程序，我们的代码在 C 语言中可能如下所示：

Consider the greatest common divisor (GCD) problem introduced at the beginning of this chapter, and shown as a function in Figure 1.2. Hypothesizing trivial I/O routines and recasting the function as a stand-alone program, our code might look like this in C:

int 主要() {

int main() {

 int i = getint(), j = getint();

 int i = getint(), j = getint();

 当 (i != j) {

 while (i != j) {

  若 (i > j) i = i − j;

  if (i > j) i = i − j;

  否则 j = j − i;

  else j = j − i;

 }

 }

 放入（i）；

 putint(i);

}

}

■

■

例 1.21

Example 1.21

GCD 程序代币

GCD program tokens

扫描和解析用于识别程序的结构，而不考虑其含义。扫描器读取字符（' i '、' n '、' t '、' '、' m '、' a '、' i '、' n '、'(' 、 ')' 等）并将它们分组为标记，这是程序的最小有意义单元。在我们的示例中，标记是

Scanning and parsing serve to recognize the structure of the program, without regard to its meaning. The scanner reads characters ('i', 'n', 't', ' ', 'm', 'a', 'i', 'n', '(',')', etc.) and groups them into tokens, which are the smallest meaningful units of the program. In our example, the tokens are

整数	主要的	（	）	{	整数	我	=
获得	（	）	，	杰	=	获得	（
）	；	尽管	（	我	!=	杰	）
{	如果	（	我	>	杰	）	我
=	我	−	杰	；	别的	杰	=
杰	−	我	；	}	普京	（	我
）	；	}

■

扫描又称为词法分析。扫描器的主要目的是通过减少输入的大小（字符比标记多得多）和删除空格等无关字符来简化解析器的任务。扫描器通常还会删除注释并用行号和列号标记标记，以便在后续阶段更容易生成良好的诊断。可以设计一个解析器以字符而不是标记作为输入 - 省去扫描器 - 但结果会很笨拙且缓慢。

Scanning is also known as lexical analysis. The principal purpose of the scanner is to simplify the task of the parser, by reducing the size of the input (there are many more characters than tokens) and by removing extraneous characters like white space. The scanner also typically removes comments and tags tokens with line and column numbers, to make it easier to generate good diagnostics in later phases. One could design a parser to take characters instead of tokens as input— dispensing with the scanner—but the result would be awkward and slow.

例 1.22

Example 1.22

上下文无关语法和解析

Context-free grammar and parsing

解析将标记组织成解析树，该解析树根据其组成部分来表示高级构造（语句、表达式、子例程等）。每个构造都是树中的一个节点；其组成部分是其子节点。树的根就是“程序”；从左到右的叶子是从扫描器接收到的标记。从整体上看，树显示了标记的排列方式组合起来形成一个有效的程序。该结构依赖于一组称为上下文无关文法的潜在递归规则。每个规则都有一个箭头符号 (→)，左侧是构造名称，右侧是可能的扩展。9^例如，在 C 语言中，while循环由关键字while后跟带括号的布尔表达式和语句组成：

Parsing organizes tokens into a parse tree that represents higher-level constructs (statements, expressions, subroutines, and so on) in terms of their constituents. Each construct is a node in the tree; its constituents are its children. The root of the tree is simply “program”; the leaves, from left to right, are the tokens received from the scanner. Taken as a whole, the tree shows how the tokens fit together to make a valid program. The structure relies on a set of potentially recursive rules known as a context-free grammar. Each rule has an arrow sign (→) with the construct name on the left and a possible expansion on the right.⁹ In C, for example, a while loop consists of the keyword while followed by a parenthesized Boolean expression and a statement:

迭代语句→ while (表达式)语句

iteration-statement → while ( expression ) statement

反过来，该语句通常是用括号括起来的列表：

The statement, in turn, is often a list enclosed in braces:

语句→复合语句

statement → compound-statement

复合语句→ { block-item-list_opt }

compound-statement → { block-item-list_opt }

在哪里

where

区块项目列表_opt →区块项目列表

block-item-list_opt → block-item-list

或者

or

块项目列表_opt → ε

block-item-list_opt → ε

和

and

区块项目列表→区块项目

block-item-list → block-item

区块项列表→区块项列表 区块项

block-item-list → block-item-list block-item

块项→声明

block-item → declaration

块项→语句

block-item → statement

这里ε代表空字符串；它表示block-item-list_opt可以简单地删除。当然，还需要更多的语法规则来解释程序的完整结构。

Here ε represents the empty string; it indicates that block-item-list_opt can simply be deleted. Many more grammar rules are needed, of course, to explain the full structure of a program.

■

■

例 1.23

Example 1.23

GCD 程序解析树

GCD program parse tree

上下文无关文法定义了语言的语法；因此，解析又称为语法分析。C 语言有许多可能的语法（事实上是无限的）；上面显示的片段取自官方语言定义 [ Int99 ] 中包含的示例语法。图 1.5显示了我们的 GCD 程序的完整解析树（基于此处未显示的完整语法）。虽然树的大小似乎令人望而生畏，但它的细节在本文的这一点上并不特别重要。重要的是(1) 每个单独的分支点代表单个语法规则的应用，以及 (2) 由此产生的复杂性更多地反映了语法而不是输入程序。大部分来自 (a) 使用诸如block_item-list和block_item-list_opt之类的人工“构造”来生成任意长度，以及 (b) 使用同样人为的赋值表达式、加法表达式、乘法表达式等来捕获算术表达式中的优先级和结合性。我们将在下一小节中看到，一旦解析完成，就可以丢弃大部分这种复杂性。■

A context-free grammar is said to define the syntax of the language; parsing is therefore known as syntax analysis. There are many possible grammars for C (an infinite number, in fact); the fragment shown above is taken from the sample grammar contained in the official language definition [Int99]. A full parse tree for our GCD program (based on a full grammar not shown here) appears in Figure 1.5. While the size of the tree may seem daunting, its details aren't particularly important at this point in the text. What is important is that (1) each individual branching point represents the application of a single grammar rule, and (2) the resulting complexity is more a reflection of the grammar than it is of the input program. Much of the bulk stems from (a) the use of such artificial “constructs” as block_item-list and block_item-list_opt to generate lists of arbitrary length, and (b) the use of the equally artificial assignment-expression, additive-expression, multiplicative-expression, and so on, to capture precedence and associativity in arithmetic expressions. We shall see in the following subsection that much of this complexity can be discarded once parsing is complete. ■

在扫描和解析过程中，编译器或解释器会检查程序的所有标记是否格式正确，以及标记序列是否符合上下文无关语法定义的语法。任何格式错误的标记（例如，C 语言中的123abc或$@foo ）都会导致扫描器生成错误消息。任何语法无效的标记序列（例如，C 语言中的A = XYZ ）都会导致解析器生成错误消息。

In the process of scanning and parsing, the compiler or interpreter checks to see that all of the program's tokens are well formed, and that the sequence of tokens conforms to the syntax defined by the context-free grammar. Any malformed tokens (e.g., 123abc or $@foo in C) should cause the scanner to produce an error message. Any syntactically invalid token sequence (e.g., A = X Y Z in C) should lead to an error message from the parser.

1.6.2 语义分析和中间代码生成

1.6.2 Semantic Analysis and Intermediate Code Generation

语义分析是发现程序中的含义。除其他功能外，语义分析器还可以识别同一标识符的多次出现是否意味着指向同一程序实体，并确保使用一致。在大多数语言中，它还会跟踪标识符和表达式的类型，以验证使用是否一致，并指导编译器后端的代码生成。

Semantic analysis is the discovery of meaning in a program. Among other things, the semantic analyzer recognizes when multiple occurrences of the same identifier are meant to refer to the same program entity, and ensures that the uses are consistent. In most languages it also tracks the types of both identifiers and expressions, both to verify consistent usage and to guide the generation of code in the back end of a compiler.

为了协助其工作，语义分析器通常会构建和维护一个符号表数据结构，该结构将每个标识符映射到已知的有关该标识符的信息。除其他事项外，此信息包括标识符的类型、内部结构（如果有）和范围（该标识符有效的程序部分）。

To assist in its work, the semantic analyzer typically builds and maintains a symbol table data structure that maps each identifier to the information known about it. Among other things, this information includes the identifier's type, internal structure (if any), and scope (the portion of the program in which it is valid).

使用符号表，语义分析器可以执行上下文无关语法和解析树的层次结构无法捕获的大量规则。例如，在 C 语言中，它会检查以确保

Using the symbol table, the semantic analyzer enforces a large variety of rules that are not captured by the hierarchical structure of the context-free grammar and the parse tree. In C, for example, it checks to make sure that

■ 每个标识符在使用前都经过声明。

■ Every identifier is declared before it is used.

■ 未在不适当的上下文中使用任何标识符（将整数作为子例程调用、将字符串添加到整数、引用错误结构类型的字段等）。

■ No identifier is used in an inappropriate context (calling an integer as a subroutine, adding a string to an integer, referencing a field of the wrong type of struct, etc.).

■ 子例程调用提供了正确数量和类型的参数。

■ Subroutine calls provide the correct number and types of arguments.

■  Switch语句臂上的标签是不同的常量。

■ Labels on the arms of a switch statement are distinct constants.

■任何具有 非void返回类型的函数都会明确返回一个值。

■ Any function with a non-void return type returns a value explicitly.

在许多前端中，语义分析器的工作采用语义动作例程的形式，当解析器意识到已经到达语法规则中的特定点时，它会调用这些例程。

In many front ends, the work of the semantic analyzer takes the form of semantic action routines, invoked by the parser when it realizes that it has reached a particular point within a grammar rule.

当然，并非所有语义规则都可以在编译时（或在解释器的前端）进行检查。那些可以检查的规则称为语言的静态语义。那些必须在运行时（或在解释器的后期阶段）检查的规则称为语言的动态语义。C 语言几乎没有动态检查（其设计者选择了性能而不是安全性）。其他语言在运行时强制执行的规则示例包括：

Of course, not all semantic rules can be checked at compile time (or in the front end of an interpreter). Those that can are referred to as the static semantics of the language. Those that must be checked at run time (or in the later phases of an interpreter) are referred to as the dynamic semantics of the language. C has very little in the way of dynamic checks (its designers opted for performance over safety). Examples of rules that other languages enforce at run time include:

■ 除非变量已被赋值，否则它们永远不会在表达式中使用^。10

■ Variables are never used in an expression unless they have been given a value.¹⁰

■ 除非指针指向一个有效对象，否则指针永远不会被取消引用。

■ Pointers are never dereferenced unless they refer to a valid object.

■ 数组下标表达式位于数组的边界内。

■ Array subscript expressions lie within the bounds of the array.

■ 算术运算不会溢出。

■ Arithmetic operations do not overflow.

当无法静态地执行规则时，编译器通常会生成代码以在运行时执行适当的检查，如果其中一项检查失败，则中止程序或生成异常。（异常将在9.4 节中讨论。）不幸的是，某些规则可能过于昂贵或无法执行，并且语言实现可能根本无法检查它们。在 Ada 中，违反此类规则的程序被称为错误的；在 C 中，其行为被称为未定义的。

When it cannot enforce rules statically, a compiler will often produce code to perform appropriate checks at run time, aborting the program or generating an exception if one of the checks then fails. (Exceptions will be discussed in Section 9.4.) Some rules, unfortunately, may be unacceptably expensive or impossible to enforce, and the language implementation may simply fail to check them. In Ada, a program that breaks such a rule is said to be erroneous; in C its behavior is said to be undefined.

例 1.24

Example 1.24

GCD 程序抽象语法树

GCD program abstract syntax tree

解析树有时也称为具体语法树，因为它完整而具体地演示了如何根据上下文无关文法规则导出特定的标记序列。但是，一旦我们知道标记序列有效，解析树中的大部分信息就与编译的后续阶段无关。在检查静态语义规则的过程中，语义分析器通常通过删除树内部的大部分“人工”节点，将解析树转换为抽象语法树（也称为AST或简称为语法树）。语义分析器还会用有用的信息注释剩余节点，例如从标识符指向其符号表条目的指针。附加到特定节点的注释称为其属性。图 1.6显示了我们的 GCD 程序的语法树。■

A parse tree is sometimes known as a concrete syntax tree, because it demonstrates, completely and concretely, how a particular sequence of tokens can be derived under the rules of the context-free grammar. Once we know that a token sequence is valid, however, much of the information in the parse tree is irrelevant to further phases of compilation. In the process of checking static semantic rules, the semantic analyzer typically transforms the parse tree into an abstract syntax tree (otherwise known as an AST, or simply a syntax tree) by removing most of the “artificial” nodes in the tree's interior. The semantic analyzer also annotates the remaining nodes with useful information, such as pointers from identifiers to their symbol table entries. The annotations attached to a particular node are known as its attributes. A syntax tree for our GCD program is shown in Figure 1.6. ■

例 1.25

Example 1.25

解释语法树

Interpreting the syntax tree

许多解释器使用带注释的语法树来表示正在运行的程序：“执行”相当于树的遍历。在我们的 GCD 程序中，解释器将从图 1.6的根节点开始，按顺序访问树主干上的语句。在第一个“ := ”节点，解释器会注意到右子节点是一个call：因此它会调用getint例程（位于符号表的第 3 个槽位）并将结果赋值给i（位于符号表的第 5 个槽位）。在第二个“ := ”节点，解释器会类似地将getint的结果赋值给j。在while节点，它会反复评估左（“≠”）子节点，如果结果为真，则递归地遍历右（ if ）子节点下的树。最后，一旦while节点的左子节点评估为假，解释器就会转到最后的call节点，并输出其结果。■

Many interpreters use an annotated syntax tree to represent the running program: “execution” then amounts to tree traversal. In our GCD program, an interpreter would start at the root of Figure 1.6 and visit, in order, the statements on the main spine of the tree. At the first “:=” node, the interpreter would notice that the right child is a call: it would therefore call the getint routine (found in slot 3 of the symbol table) and assign the result into i (found in slot 5 of the symbol table). At the second “:=” node the interpreter would similarly assign the result of getint into j. At the while node it would repeatedly evaluate the left (“≠”) child and, if the result was true, recursively walk the tree under the right (if) child. Finally, once the while node's left child evaluated to false, the interpreter would move on to the final call node, and output its result. ■

在许多编译器中，带注释的语法树构成了从前端传递到后端的中间形式。在其他编译器中，语义分析以遍历树（通常是单次遍历）结束，从而生成其他中间形式。一种常见的中间形式由一个控制流图组成，其节点类似于简单理想化机器的汇编语言片段。我们将在第 15 章进一步考虑这个选项，其中我们的 GCD 程序的控制流图如图15.3所示。在一组相关的编译器中，几种语言的前端和几台机器的后端将共享一个通用的中间形式。

In many compilers, the annotated syntax tree constitutes the intermediate form that is passed from the front end to the back end. In other compilers, semantic analysis ends with a traversal of the tree (typically single pass) that generates some other intermediate form. One common such form consists of a control flow graph whose nodes resemble fragments of assembly language for a simple idealized machine. We will consider this option further in Chapter 15, where a control flow graph for our GCD program appears in Figure 15.3. In a suite of related compilers, the front ends for several languages and the back ends for several machines would share a common intermediate form.

1.6.3 目标代码生成

1.6.3 Target Code Generation

例 1.26

Example 1.26

GCD程序汇编代码

GCD program assembly code

编译器的代码生成阶段将中间形式翻译成目标语言。根据语法树中包含的信息，生成正确的代码通常不是一项艰巨的任务（生成好的代码更难，我们将在1.6.4 节中看到）。为了生成汇编语言或机器语言，代码生成器遍历符号表以将位置分配给变量，然后遍历程序的中间表示，为变量引用生成加载和存储，中间穿插适当的算术运算、测试和分支。图 1.7显示了我们的 GCD 示例的简单代码，以 x86 汇编语言编写。它是由一个简单的教学编译器自动生成的。

The code generation phase of a compiler translates the intermediate form into the target language. Given the information contained in the syntax tree, generating correct code is usually not a difficult task (generating good code is harder, as we shall see in Section 1.6.4). To generate assembly or machine language, the code generator traverses the symbol table to assign locations to variables, and then traverses the intermediate representation of the program, generating loads and stores for variable references, interspersed with appropriate arithmetic operations, tests, and branches. Naive code for our GCD example appears in Figure 1.7, in x86 assembly language. It was generated automatically by a simple pedagogical compiler.

汇编语言助记符可能看起来有点神秘，但每行上的注释（不是由编译器生成的！）应该可以使图 1.6和1.7之间的对应关系大致明显。一些提示：esp、ebp、eax、ebx和edi是寄存器（特殊存储位置，数量有限，可以非常快速地访问）。−8(%ebp)指的是地址在寄存器ebp中的位置之前 8 个字节的内存位置；在这个程序中，ebp用作我们可以从中找到变量i和j的基数。子程序调用指令的参数通过将它推送到堆栈上来传递，其中esp是堆栈顶部指针。返回值返回到寄存器eax中。算术运算用运算结果覆盖其第二个参数^。11

The assembly language mnemonics may appear a bit cryptic, but the comments on each line (not generated by the compiler!) should make the correspondence between Figures 1.6 and 1.7 generally apparent. A few hints: esp, ebp, eax, ebx, and edi are registers (special storage locations, limited in number, that can be accessed very quickly). −8(%ebp) refers to the memory location 8 bytes before the location whose address is in register ebp; in this program, ebp serves as a base from which we can find variables i and j. The argument to a subroutine call instruction is passed by pushing it onto a stack, for which esp is the top-of-stack pointer. The return value comes back in register eax. Arithmetic operations overwrite their second argument with the result of the operation.¹¹

■

■

代码生成器通常会将符号表包含在目标代码的不可执行部分中，以供符号调试器稍后使用。

Often a code generator will save the symbol table for later use by a symbolic debugger, by including it in a nonexecutable part of the target code.

1.7 总结和结束语

1.7 Summary and Concluding Remarks

在本章中，我们介绍了编程语言设计和实现的研究。我们考虑了为什么有这么多语言，是什么让它们成功或失败，如何对它们进行分类以供研究，以及读者可能从这项研究中获得什么好处。我们注意到语言设计和语言实现是紧密相连的。显然，实现必须符合语言的规则。同时，语言设计者必须考虑实现各种功能的难易程度，以及可能产生什么样的性能。

In this chapter we introduced the study of programming language design and implementation. We considered why there are so many languages, what makes them successful or unsuccessful, how they may be categorized for study, and what benefits the reader is likely to gain from that study. We noted that language design and language implementation are intimately tied to one another. Obviously an implementation must conform to the rules of the language. At the same time, a language designer must consider how easy or difficult it will be to implement various features, and what sort of performance is likely to result.

语言实现通常分为基于解释的实现和基于编译的实现。然而，我们注意到，这两种方法之间的区别并不明显，大多数实现都包含这两种方法的一点。一般来说，如果执行之前有一个翻译步骤，该步骤 (1) 全面分析程序的结构（语法）和含义（语义），并且 (2) 生成一个形式截然不同的等效程序，那么我们就说该语言是编译的。本书中的大部分实现材料都与编译有关。

Language implementations are commonly differentiated into those based on interpretation and those based on compilation. We noted, however, that the difference between these approaches is fuzzy, and that most implementations include a bit of each. As a general rule, we say that a language is compiled if execution is preceded by a translation step that (1) fully analyzes both the structure (syntax) and meaning (semantics) of the program, and (2) produces an equivalent program in a significantly different form. The bulk of the implementation material in this book pertains to compilation.

编译器通常由一系列阶段组成。前几个阶段（扫描、解析和语义分析）用于分析源程序。这些阶段统称为编译器的前端。最后几个阶段（目标代码生成和针对机器的代码改进）称为后端。它们用于构建目标程序（最好是快速程序），其语义与源代码相匹配。在前端和后端之间，优秀的编译器会执行大量与机器无关的代码改进；这个“中端”的阶段通常构成编译器的大部分代码，并占其执行时间的大部分。

Compilers are generally structured as a series of phases. The first few phases— scanning, parsing, and semantic analysis—serve to analyze the source program. Collectively these phases are known as the compiler's front end. The final few phases—target code generation and machine-specific code improvement—are known as the back end. They serve to build a target program—preferably a fast one—whose semantics match those of the source. Between the front end and the back end, a good compiler performs extensive machine-independent code improvement; the phases of this “middle end” typically comprise the bulk of the code of the compiler, and account for most of its execution time.

第 3、6、7、8、9 和 10 章是本书其余部分的核心。这些章从程序员和语言实现者的角度介绍了语言设计的基本问题。为了支持实现的讨论，第2章和第4章比本介绍中更详细地描述了编译器前端。第 5 章概述了汇编级架构。第 15至17章讨论了编译器后端，包括汇编器和链接器、运行时系统和代码改进技术。第11至14章介绍了其他语言范式。附录 A列出了文中提到的主要编程语言，以及家谱和参考书目。附录 B包含“设计和实现”边栏列表；附录 C包含编号示例列表。

Chapters 3, 6, 7, 8, 9, and 10 form the core of the rest of this book. They cover fundamental issues of language design, both from the point of view of the programmer and from the point of view of the language implementor. To support the discussion of implementations, Chapters 2 and 4 describe compiler front ends in more detail than has been possible in this introduction. Chapter 5 provides an overview of assembly-level architecture. Chapters 15 through 17 discuss compiler back ends, including assemblers and linkers, run-time systems, and code improvement techniques. Additional language paradigms are covered in Chapters 11 through 14. Appendix A lists the principal programming languages mentioned in the text, together with a genealogical chart and bibliographic references. Appendix B contains a list of “Design & Implementation” sidebars; Appendix C contains a list of numbered examples.

1.8 练习

1.8 Exercises

1.1 计算机程序中的错误可以根据检测到的时间进行分类，如果在编译时检测到错误，则根据编译器的哪个部分检测到错误进行分类。使用您最喜欢的命令式语言，给出以下每个示例。

1.1 Errors in a computer program can be classified according to when they are detected and, if they are detected at compile time, what part of the compiler detects them. Using your favorite imperative language, give an example of each of the following.

（a） 扫描仪检测到词汇错误

(a) A lexical error, detected by the scanner

（b） 解析器检测到语法错误

(b) A syntax error, detected by the parser

（c） 通过语义分析检测到的静态语义错误

(c) A static semantic error, detected by semantic analysis

（d） 编译器生成的代码检测到的动态语义错误

(d) A dynamic semantic error, detected by code generated by the compiler

（e） 编译器无法捕获的错误，也无法轻易生成代码来捕获的错误（这应该是违反语言定义的，而不仅仅是程序错误）

(e) An error that the compiler can neither catch nor easily generate code to catch (this should be a violation of the language definition, not just a program bug)

1.2 再次考虑 Niklaus Wirth 分发的 Pascal 工具集（示例 1.15）。成功构建机器语言版本的 Pascal 编译器后，原则上可以丢弃 P 代码解释器和 P 代码版本的编译器。为什么人们会选择不这样做呢？

1.2 Consider again the Pascal tool set distributed by Niklaus Wirth (Example 1.15). After successfully building a machine language version of the Pascal compiler, one could in principle discard the P-code interpreter and the P-code version of the compiler. Why might one choose not to do so?

1.3  Fortran 和 C 等命令式语言通常是编译型的，而脚本语言通常是解释型的，因为脚本语言中的许多问题直到运行时才能解决。解释仅仅是编译不可行时“不得不做的事情”吗？还是即使有编译器可用，解释语言实际上也有一些优势？

1.3 Imperative languages like Fortran and C are typically compiled, while scripting languages, in which many issues cannot be settled until run time, are typically interpreted. Is interpretation simply what one “has to do” when compilation is infeasible, or are there actually some advantages to interpreting a language, even when a compiler is available?

1.4 示例 1.20中的gcd程序也可以这样写：int main() { int i = getint(), j = getint(); while (i != j) { if (i > j) i = i % j; else j = j % i; } putint(i); }这个程序计算的结果是否相同？如果不是，你能修复它吗？在什么情况下你认为其中一个会更快？

 

  

  

   

   

  

  

 

1.4 The gcd program of Example 1.20 might also be written

 int main() {

  int i = getint(), j = getint();

  while (i != j) {

   if (i > j) i = i % j;

   else j = j % i;

  }

  putint(i);

 }

Does this program compute the same result? If not, can you fix it? Under what circumstances would you expect one or the other to be faster?

1.5 扩展示例 1.25 ，跟踪对输入 12 和 8 的gcd程序的解释。哪些语法树节点被访问，按什么顺序访问？

1.5 Expanding on Example 1.25, trace an interpretation of the gcd program on the inputs 12 and 8. Which syntax tree nodes are visited, in which order?

1.6 解释和代码生成都可以通过遍历语法树来完成。比较这两种遍历。它们在哪些方面相似/不同？

1.6 Both interpretation and code generation can be performed by traversal of a syntax tree. Compare these two kinds of traversals. In what ways are they similar/different?

1.7 在你的 C 语言本地实现中，整数的大小限制是多少？如果发生算术溢出，会发生什么？大小限制对程序从一台机器/编译器到另一台机器/编译器的可移植性有何影响？对于 Java、Ada、Pascal 和 Scheme，这些问题的答案有何不同？（您可能需要查找手册。）

1.7 In your local implementation of C, what is the limit on the size of integers? What happens in the event of arithmetic overflow? What are the implications of size limits on the portability of programs from one machine/compiler to another? How do the answers to these questions differ for Java? For Ada? For Pascal? For Scheme? (You may need to find a manual.)

1.8  Unix make实用程序允许程序员指定程序中单独编译的部分之间的依赖关系。如果文件A依赖于文件B，并且文件B被修改，则make推断必须重新编译A ，以防对B的任何更改会影响为A生成的代码。这种依赖管理有多准确？在什么情况下会导致不必要的工作？在什么情况下，它会无法重新编译需要重新编译的内容？

1.8 The Unix make utility allows the programmer to specify dependences among the separately compiled pieces of a program. If file A depends on file B and file B is modified, make deduces that A must be recompiled, in case any of the changes to B would affect the code produced for A. How accurate is this sort of dependence management? Under what circumstances will it lead to unnecessary work? Under what circumstances will it fail to recompile something that needs to be recompiled?

1.9 为什么很难判断程序是否正确？如何查找代码中的错误？测试可以发现哪些错误？哪些错误不能？（有关程序正确性的更正式概念，请参阅第 4 章末尾的参考书目注释。）

1.9 Why is it difficult to tell whether a program is correct? How do you go about finding bugs in your code? What kinds of bugs are revealed by testing? What kinds of bugs are not? (For more formal notions of program correctness, see the bibliographic notes at the end of Chapter 4.)

1.9 探索

1.9 Explorations

1.10

1.10

(a) 您学习的第一门编程语言是什么？如果您选择了它，为什么会选择它？如果是别人为您选择的，您认为他们为什么会选择它？您觉得该语言的哪些部分最难学？

(a) What was the first programming language you learned? If you chose it, why did you do so? If it was chosen for you by others, why do you think they chose it? What parts of the language did you find the most difficult to learn?

(b) 对于你最熟悉的语言（这可能是也可能不是你学到的第一门语言），列出三件你希望设计不同的事物。你认为它们为什么会这样设计？如果有机会重来，你会如何修复它们？会有什么负面影响吗，例如在编译器复杂性或程序执行速度方面？

(b) For the language with which you are most familiar (this may or may not be the first one you learned), list three things you wish had been differently designed. Why do you think they were designed the way they were? How would you fix them if you had the chance to do it over? Would there be any negative consequences, for example in terms of compiler complexity or program execution speed?

1.11 找一个主要使用图 1.1中不同类别语言的同学。（例如，如果你主要使用 C 语言，你可以找一个有 Lisp 经验的人。）比较一下笔记。在你们各自的经历中，编程最简单和最困难的方面是什么？选择一个简单的问题（例如，排序或识别图中的连通分量），并使用你最喜欢的每种语言来解决它。哪种解决方案更优雅（你们两个同意吗）？哪个更快？为什么？

1.11 Get together with a classmate whose principal programming experience is with a language in a different category of Figure 1.1. (If your experience is mostly in C, for example, you might search out someone with experience in Lisp.) Compare notes. What are the easiest and most difficult aspects of programming, in each of your experiences? Pick a simple problem (e.g., sorting, or identification of connected components in a graph) and solve it using each of your favorite languages. Which solution is more elegant (do the two of you agree)? Which is faster? Why?

1.12 

1.12 

（a） 如果您可以访问 Unix 系统，请使用−S命令行标志编译一个简单的程序。向生成的汇编语言文件添加注释以解释每条指令的用途。

(a) If you have access to a Unix system, compile a simple program with the −S command-line flag. Add comments to the resulting assembly language file to explain the purpose of each instruction.

（b） 现在使用-o命令行标志生成可重定位目标文件。使用适当的本地工具（特别是查找nm、objdump或使用符号调试器（例如gdb或dbx）来识别每行汇编程序对应的机器语言。

(b) Now use the −o command-line flag to generate a relocatable object file. Using appropriate local tools (look in particular for nm, objdump, or a symbolic debugger like gdb or dbx), identify the machine language corresponding to each line of assembler.

(c) 使用nm、objdump或类似工具，识别目标文件中未定义的外部符号。现在运行编译器直至完成，以生成可执行文件。最后，再次运行nm或objdump以查看部分 (b) 中的符号发生了什么。它们来自哪里 — 链接器如何解析它们？

(c) Using nm, objdump, or a similar tool, identify the undefined external symbols in your object file. Now run the compiler to completion, to produce an executable file. Finally, run nm or objdump again to see what has happened to the symbols in part (b). Where did they come from—how did the linker resolve them?

(d)使用 -v命令行标志再次运行编译器直至完成。您应该看到描述编译过程中调用的各种子程序的消息（某些编译器对此选项使用不同的字母；请查看手册页）。子程序可能包括预处理器、编译器本身的单独传递（通常为两次）、可能还有汇编器和链接器。如果可能，请自己单独运行这些子程序。它们中的哪一个生成了前面子问题中描述的文件？解释调用子程序的各种命令行标志的用途。

(d) Run the compiler to completion one more time, using the −v command-line flag. You should see messages describing the various subprograms invoked during the compilation process (some compilers use a different letter for this option; check the man page). The subprograms may include a preprocessor, separate passes of the compiler itself (often two), probably an assembler, and the linker. If possible, run these subprograms yourself, individually. Which of them produce the files described in the previous subquestions? Explain the purpose of the various command-line flags with which the subprograms were invoked.

1.13 编写一个程序，该程序会犯动态语义错误（例如，除以零、访问数组末尾以外的内容、取消引用空指针）。运行此程序时会发生什么？编译器是否为您提供了控制发生情况的选项？设计一个实验来评估运行时语义检查的成本。如果可能，请使用多种语言或编译器尝试此练习。

1.13 Write a program that commits a dynamic semantic error (e.g., division by zero, access off the end of an array, dereference of a null pointer). What happens when you run this program? Does the compiler give you options to control what happens? Devise an experiment to evaluate the cost of runtime semantic checks. If possible, try this exercise with more than one language or compiler.

1.14  C 语言被认为是一种相对“不安全”的高级语言。例如：它允许程序员以比其“更安全”的同类语言更多的方式混合不同大小和类型的操作数。Unix lint实用程序可用于搜索 C 程序中潜在的不安全构造。实际上，其他语言中编译器强制执行的许多规则在 C 语言中是可选的，并且由单独的程序强制执行（如果需要）。您如何看待这种方法？这是一个好主意吗？为什么或为什么不？

1.14 C has a reputation for being a relatively “unsafe” high-level language. For example: it allows the programmer to mix operands of different sizes and types in many more ways than its “safer” cousins. The Unix lint utility can be used to search for potentially unsafe constructs in C programs. In effect, many of the rules that are enforced by the compiler in other languages are optional in C, and are enforced (if desired) by a separate program. What do you think of this approach? Is it a good idea? Why or why not?

1.15 使用互联网搜索引擎或杂志索引服务，了解 Java 和 C# 的历史，包括 Sun 和 Microsoft 在 Java 标准化方面的冲突。有人声称 C# 至少在一定程度上是 Microsoft 试图破坏 Java 的传播。其他人则指出这两种语言在哲学和实践上的差异，并认为 C# 的优势不止于此。事后看来，您如何看待 Microsoft 寻求替代 Java 的决定？

1.15 Using an Internet search engine or magazine indexing service, read up on the history of Java and C#, including the conflict between Sun and Microsoft over Java standardization. Some have claimed that C# was, at least in part, an attempt by Microsoft to undermine the spread of Java. Others point to philosophical and practical differences between the languages, and argue that C# more than stands on its merits. In hindsight, how would you characterize Microsoft's decision to pursue an alternative to Java?

1.10 书目注释

1.10 Bibliographic Notes

本书中面向编译器的章节试图传达编译器的功能，而不是解释如何构建编译器。其他文本中可以找到更详细的信息。主要选项包括 Aho 的作品等人 [ ALSU07 ]、Cooper 和 Torczon [ CT04 ] 以及 Fischer 等人 [ FCL10 ] 的著作。其他优秀但不太流行的著作包括 Appel [ App97 ] 和 Grune 等人 [ GBJ ⁺ 12 ] 的著作。关于编程语言设计的热门著作包括 Louden [ LL12 ]、Sebesta [ Seb15 ] 和 Sethi [ Set96 ]的著作。

The compiler-oriented chapters of this book attempt to convey a sense of what the compiler does, rather than explaining how to build one. A much greater level of detail can be found in other texts. Leading options include the work of Aho et al. [ALSU07], Cooper and Torczon [CT04], and Fischer et al. [FCL10]. Other excellent, though less current texts include those of Appel [App97] and Grune et al. [GBJ⁺12]. Popular texts on programming language design include those of Louden [LL12], Sebesta [Seb15], and Sethi [Set96].

关于编程语言历史的一些最好的信息可以在计算机协会在 1978、1993 和 2007 年主办的会议记录中找到 [ Wex78、Ass93、Ass07 ]。另一个很好的参考资料是 Horowitz 1987 年的文本 [ Hor87 ]。在季刊《 IEEE 计算史年鉴》中可以找到更广泛的历史资料。鉴于个人品味在编程语言设计中的重要性，一些语言比较不可避免地会带有措辞强烈的意见。早期的例子包括 Dijkstra [ Dij82 ]、Hoare [ Hoa81 ]、Kernighan [ Ker81 ] 和 Wirth [ Wir85a ]的著作。

Some of the best information on the history of programming languages can be found in the proceedings of conferences sponsored by the Association for Computing Machinery in 1978,1993, and 2007 [Wex78, Ass93, Ass07]. Another excellent reference is Horowitz's 1987 text [Hor87]. A broader range of historical material can be found in the quarterly IEEE Annals of the History of Computing. Given the importance of personal taste in programming language design, it is inevitable that some language comparisons should be marked by strongly worded opinions. Early examples include the writings of Dijkstra [Dij82], Hoare [Hoa81], Kernighan [Ker81], and Wirth [Wir85a].

许多现代软件开发都是在集成编程环境中进行的。这些环境的有影响力的前身包括 Symbolics Corp. 的 Genera Common Lisp 环境 [ WMWM87 ] 以及 Xerox Palo Alto 研究中心的 Smalltalk [ Gol84 ]、Interlisp [ TM81 ] 和 Cedar [ SZBH86 ] 环境。

Much modern software development takes place in integrated programming environments. Influential precursors to these environments include the Genera Common Lisp environment from Symbolics Corp. [WMWM87] and the Smalltalk [Gol84], Interlisp [TM81], and Cedar [SZBH86] environments at the Xerox Palo Alto Research Center.

2.1 指定语法：正则表达式和上下文无关文法

2.1 Specifying Syntax: Regular Expressions and Context-Free Grammars

语法的正式规范需要一套规则。语法的复杂程度（表达能力）取决于我们可以使用哪种规则。事实证明，我们直观地认为的标记可以用三种正式规则从单个字符构造出来：连接、交替（在一组有限的备选方案中进行选择）和所谓的“克莱尼闭包”（重复任意次数）。指定我们直观认为的语法的其余大部分内容需要一种额外的规则：递归（从相同构造的更简单实例创建构造）。任何可以根据前三个规则定义的字符串集合称为正则集，有时也称为正则语言。正则集由正则表达式生成并被扫描器识别。任何可以通过添加递归来定义的字符串集合称为上下文无关语言(CFL)。上下文无关语言由上下文无关语法(CFG)生成并被解析器识别。（这里的术语可能令人困惑。“语言”一词的含义差异很大，取决于我们谈论的是“形式”语言 [例如，正则语言或上下文无关语言] 还是编程语言。形式语言只是一组字符串，没有伴随的语义。）

Formal specification of syntax requires a set of rules. How complicated (expressive) the syntax can be depends on the kinds of rules we are allowed to use. It turns out that what we intuitively think of as tokens can be constructed from individual characters using just three kinds of formal rules: concatenation, alternation (choice among a finite set of alternatives), and so-called “Kleene closure” (repetition an arbitrary number of times). Specifying most of the rest of what we intuitively think of as syntax requires one additional kind of rule: recursion (creation of a construct from simpler instances of the same construct). Any set of strings that can be defined in terms of the first three rules is called a regular set, or sometimes a regular language. Regular sets are generated by regular expressions and recognized by scanners. Any set of strings that can be defined if we add recursion is called a context-free language (CFL). Context-free languages are generated by context-free grammars (CFGs) and recognized by parsers. (Terminology can be confusing here. The meaning of the word “language” varies greatly, depending on whether we're talking about “formal” languages [e.g., regular or context-free], or programming languages. A formal language is just a set of strings, with no accompanying semantics.)

2.1.3 推导和解析树

2.1.3 Derivations and Parse Trees

上下文无关语法向我们展示了如何生成语法上有效的终结符字符串：从起始符号开始。选择一个起始符号在左侧的产生式；用该产生式的右侧替换起始符号。现在在结果字符串中选择一个非终结符A ，选择一个左侧有A的产生式P ，用P的右侧替换A。重复此过程，直到没有非终结符剩余。

A context-free grammar shows us how to generate a syntactically valid string of terminals: Begin with the start symbol. Choose a production with the start symbol on the left-hand side; replace the start symbol with the right-hand side of that production. Now choose a nonterminal A in the resulting string, choose a production P with A on its left-hand side, and replace A with the right-hand side of P. Repeat this process until no nonterminals remain.

例 2.6

Example 2.6

斜率 * x + 截距的推导

Derivation of slope * x + intercept

举个例子，我们可以使用表达式语法来生成字符串“slope * x +略微截距”：

As an example, we can use our grammar for expressions to generate the string “slope * x + intercept”:

expr ⇒ expr op expr

expr ⇒ expr op expr

 ⇒ expr op id

 ⇒ expr op id

 ⇒表达式+ id

 ⇒ expr + id

 ⇒ expr op expr + id

 ⇒ expr op expr + id

 ⇒ expr op id + id

 ⇒ expr op id + id

 ⇒表达式* id + id

 ⇒ expr * id + id

 ⇒ id（斜率）* id（x）+ id（截距）

 ⇒ id (slope) * id (x) + id (intercept)

⇒元符号通常发音为“derives”。它表示右侧是通过使用产生式替换左侧的一些非终结符而得到的。在每一行中，我们都用下划线标出了在下一行中被替换的符号A。 ■

The ⇒ metasymbol is often pronounced “derives.” It indicates that the right-hand side was obtained by using a production to replace some nonterminal in the left-hand side. At each line we have underlined the symbol A that is replaced in the following line. ■

一系列替换操作，展示如何从起始符号导出一串终结符，称为一次推导。沿途的每一串符号称为一个句型。最终的句型仅由终结符组成，称为推导的产物。我们有时会省略中间步骤，写为expr ⇒* slope * x + interval，其中元符号⇒*表示“在零次或多次替换后导出”。在这个特定的推导中，我们在每个步骤都选择用某个产生式的右边替换最右边的非终结符。这种替换策略导致最右边的推导。还有许多其他可能的推导，包括最左边的推导和介于两者之间的选项。

A series of replacement operations that shows how to derive a string of terminals from the start symbol is called a derivation. Each string of symbols along the way is called a sentential form. The final sentential form, consisting of only terminals, is called the yield of the derivation. We sometimes elide the intermediate steps and write expr ⇒* slope * x + intercept, where the metasymbol ⇒* means “derives after zero or more replacements.” In this particular derivation, we have chosen at each step to replace the right-most nonterminal with the right-hand side of some production. This replacement strategy leads to a right-most derivation. There are many other possible derivations, including left-most and options in-between.

我们在第 1 章中看到，我们可以用解析树的形式来表示推导。解析树的根是语法的起始符号。树的叶子是其收益。每个内部节点及其子节点都表示产生式的使用。

We saw in Chapter 1 that we can represent a derivation graphically as a parse tree. The root of the parse tree is the start symbol of the grammar. The leaves of the tree are its yield. Each internal node, together with its children, represents the use of a production.

例 2.7

Example 2.7

解析斜率 * x + 截距的树

Parse trees for slope * x + intercept

图 2.1显示了示例表达式的解析树。这棵树并不唯一。在树的第二层，我们可以选择将运算符变成 * 而不是 +，并进一步扩展右侧的表达式，而不是左侧的表达式（参见图 2.2）。允许为一些终端字符串构建多于一棵解析树被称为是歧义的。歧义在尝试构建解析器时会成为一个问题：它需要一些额外的机制来推动在同样可接受的替代方案之间做出选择。■

A parse tree for our example expression appears in Figure 2.1. This tree is not unique. At the second level of the tree, we could have chosen to turn the operator into a * instead of a +, and to further expand the expression on the right, rather than the one on the left (see Figure 2.2). A grammar that allows the construction of more than one parse tree for some string of terminals is said to be ambiguous. Ambiguity turns out to be a problem when trying to build a parser: it requires some extra mechanism to drive a choice between equally acceptable alternatives. ■

稍加思考就会发现，对于任何给定的上下文无关语言，都有无数个上下文无关语法。9^但是，有些语法比其他语法有用得多。在本文中，我们将避免使用歧义语法（尽管大多数解析器生成器都允许使用它们，方法是使用消歧规则）。我们还将避免使用所谓的无用符号：不能生成任何终结符串的非终结符，或不能出现在任何派生结果中的终结符。

A moment's reflection will reveal that there are infinitely many context-free grammars for any given context-free language.⁹ Some grammars, however, are much more useful than others. In this text we will avoid the use of ambiguous grammars (though most parser generators allow them, by means of disambiguating rules). We will also avoid the use of so-called useless symbols: nonterminals that cannot generate any string of terminals, or terminals that cannot appear in the yield of any derivation.

在为一种编程语言设计文法时，我们一般会尝试找到一种能够反映程序内部结构的文法，以便编译器的其余部分能够使用它。（我们将在2.3.2 节中看到，我们还会尝试找到一种能够高效解析的文法，这可能有点困难。）结构在算术表达式中尤为重要，我们可以使用产生式来捕获各种运算符的结合性和优先级。结合性告诉我们，大多数语言中的运算符都是从左到右分组的，因此10 − 4 − 3表示(10 − 4) − 3 ，而不是10 − (4 − 3)。优先级告诉我们，大多数语言中的乘法和除法比加法和减法分组更紧密，因此3 + 4 * 5表示3 + (4 * 5)，而不是(3 + 4) * 5。 （这些规则并不通用；我们将在第 6.1.1 节中再次考虑它们。）

When designing the grammar for a programming language, we generally try to find one that reflects the internal structure of programs in a way that is useful to the rest of the compiler. (We shall see in Section 2.3.2 that we also try to find one that can be parsed efficiently, which can be a bit of a challenge.) One place in which structure is particularly important is in arithmetic expressions, where we can use productions to capture the associativity and precedence of the various operators. Associativity tells us that the operators in most languages group left to right, so that 10 − 4 − 3 means (10 − 4) − 3 rather than 10 − (4 − 3). Precedence tells us that multiplication and division in most languages group more tightly than addition and subtraction, so that 3 + 4 * 5 means 3 + (4 * 5) rather than (3 + 4) * 5. (These rules are not universal; we will consider them again in Section 6.1.1.)

例 2.8

Example 2.8

具有优先级和结合性的表达式语法

Expression grammar with precedence and associativity

以下是我们的表达语法的更好版本：

Here is a better version of our expression grammar:

1. expr → term | expr add_op term

1. expr → term | expr add_op term

2.术语→因子|术语 mult_op 因子

2. term → factor | term mult_op factor

3.因子→ id | 数字 | −因子| ( expr )

3. factor → id | number | − factor | ( expr )

4.添加操作→ + | −

4. add_op → + | −

5.多操作→ * | /

5. mult_op → * | /

这个文法是明确的。它以factor、term和expr相互构建的方式捕获优先级，每个级别上都有不同的运算符。它在第 1 行和第 2 行的后半部分捕获结合性，即将 sub expr和 sub term构建在运算符的左侧，而不是右侧。在图 2.3中，我们可以看到如何在文法中构建优先级概念，从而清楚地表明在3 + 4 * 5中乘法的分组比加法更紧密，即使没有括号也是如此。在图 2.4中，我们可以看到减法更紧密地向左分组，因此10 − 4 − 3的计算结果为3，而不是9。 ■

This grammar is unambiguous. It captures precedence in the way factor, term, and expr build on one another, with different operators appearing at each level. It captures associativity in the second halves of lines 1 and 2, which build subexprs and sub terms to the left of the operator, rather than to the right. In Figure 2.3, we can see how building the notion of precedence into the grammar makes it clear that multiplication groups more tightly than addition in 3 + 4 * 5, even without parentheses. In Figure 2.4, we can see that subtraction groups more tightly to the left, so that 10 − 4 − 3 would evaluate to 3, rather than to 9. ■

检查你的理解

Check Your Understanding

1. 句法和语义有什么区别？

1. What is the difference between syntax and semantics?

2. 可以使用哪三种基本运算从较简单的正则表达式构建复杂的正则表达式？

2. What are the three basic operations that can be used to build complex regular expressions from simpler regular expressions?

3. 上下文无关文法除了正则表达式的三种操作之外，还提供了哪些附加操作？

3. What additional operation (beyond the three of regular expressions) is provided in context-free grammars?

4. 什么是Backus-Naur 范式？它是何时以及为何被发明的？

4. What is Backus-Naur form? When and why was it devised?

5. 说出一种缩进影响程序语法的语言。

5. Name a language in which indentation affects program syntax.

6. 在讨论上下文无关语言时，什么是派生？什么是句子形式？

6. When discussing context-free languages, what is a derivation? What is a sentential form?

7. 最右推导和最左推导有什么区别？

7. What is the difference between a right-most derivation and a left-most derivation?

8. 上下文无关文法具有歧义是什么意思？

8. What does it mean for a context-free grammar to be ambiguous?

9. 什么是结合性和优先级？为什么它们在解析树中很重要？

9. What are associativity and precedence? Why are they significant in parse trees?

2.2 扫描

2.2 Scanning

编程语言的扫描器和解析器共同负责发现程序的语法结构。这个发现过程或语法分析是将程序翻译成目标语言的等效程序的必要的第一步。（这也是直接解释程序的第一步。一般来说，在本书的其余部分，我们将重点关注编译，而不是解释。我们将要讨论的大部分内容要么明显适用于解释，要么显然与解释无关。）

Together, the scanner and parser for a programming language are responsible for discovering the syntactic structure of a program. This process of discovery, or syntax analysis, is a necessary first step toward translating the program into an equivalent program in the target language. (It's also the first step toward interpreting the program directly. In general, we will focus on compilation, rather than interpretation, for the remainder of the book. Most of what we shall discuss either has an obvious application to interpretation, or is obviously irrelevant to it.)

通过将输入字符分组为标记，扫描器大大减少了计算量更大的解析器必须检查的单个项目的数量。此外，扫描器通常会删除注释（因此解析器不必担心它们出现在整个上下文无关语法中 - 参见练习 2.20）；保存“有趣”标记的文本，如标识符、字符串和数字文字；并使用行号和列号标记标记，以便在后续阶段更轻松地生成高质量的错误消息。

By grouping input characters into tokens, the scanner dramatically reduces the number of individual items that must be inspected by the more computationally intensive parser. In addition, the scanner typically removes comments (so the parser doesn't have to worry about them appearing throughout the context-free grammar—see Exercise 2.20); saves the text of “interesting” tokens like identifiers, strings, and numeric literals; and tags tokens with line and column numbers, to make it easier to generate high-quality error messages in subsequent phases.

例 2.10

Example 2.10

计算器令牌的临时扫描器

An ad hoc scanner for calculator tokens

我们如何识别计算器语言的标记？最简单的方法是完全临时的。伪代码如图2.5所示。我们可以按照自己喜欢的方式构造代码，但首先检查更简单、更常见的情况，在需要时提前查看，并为注释和标识符和数字等长标记嵌入循环似乎是合理的。

How might we go about recognizing the tokens of our calculator language? The simplest approach is entirely ad hoc. Pseudocode appears in Figure 2.5. We can structure the code however we like, but it seems reasonable to check the simpler and more common cases first, to peek ahead when we need to, and to embed loops for comments and for long tokens such as identifiers and numbers.

找到标记后，扫描器返回到解析器。再次调用时，它会从头开始重复该算法，使用下一个可用的输入字符（包括上次查看但未使用的字符）。■

After finding a token the scanner returns to the parser. When invoked again it repeats the algorithm from the beginning, using the next available characters of input (including any that were peeked at but not consumed the last time). ■

通常，我们在每次调用扫描器时都接受最长的标记。因此foobar始终是foobar，而永远不会是f或foo或 f oob。更重要的是，在 C 语言等语言中，3.14159是实数，而永远不会是3、 . 和14159。空格（空格、制表符、换行符、注释）通常会被忽略，除非它分隔标记（例如，foo bar与foobar不同）。

As a rule, we accept the longest possible token in each invocation of the scanner. Thus foobar is always foobar and never f or foo or foob. More to the point, in a language like C, 3.14159 is a real number and never 3, ., and 14159. White space (blanks, tabs, newlines, comments) is generally ignored, except to the extent that it separates tokens (e.g., foo bar is different from foobar).

图 2.5可以相当容易地扩展以概述某些较大编程语言的扫描器。然后可以手工充实结果以创建某些实现语言的代码。生产编译器通常使用这种临时扫描器；代码快速而紧凑。然而，在语言开发过程中，通常最好以更结构化的方式构建扫描器，作为有限自动机的显式表示。有限自动机可以从一组正则表达式自动生成，从而当标记定义发生变化时可以轻松地重新生成扫描器。

Figure 2.5 could be extended fairly easily to outline a scanner for some larger programming language. The result could then be fleshed out, by hand, to create code in some implementation language. Production compilers often use such ad hoc scanners; the code is fast and compact. During language development, however, it is usually preferable to build a scanner in a more structured way, as an explicit representation of a finite automaton. Finite automata can be generated automatically from a set of regular expressions, making it easy to regenerate a scanner when token definitions change.

例 2.11

Example 2.11

计算器扫描仪的有限自动机

Finite automaton for a calculator scanner

图 2.6以图形形式显示了我们的计算器语言的标记自动机。自动机以独特的初始状态开始。然后，它根据下一个可用的输入字符从一个状态移动到另一个状态。当它到达指定的一组最终状态之一时，它会识别与该状态关联的标记。“最长可能的标记”规则意味着，只有当下一个字符不能用于继续当前标记时，扫描器才会返回到解析器。■

An automaton for the tokens of our calculator language appears in pictorial form in Figure 2.6. The automaton starts in a distinguished initial state. It then moves from state to state based on the next available character of input. When it reaches one of a designated set of final states it recognizes the token associated with that state. The “longest possible token” rule means that the scanner returns to the parser only when the next character cannot be used to continue the current token. ■

2.2.1 生成有限自动机

2.2.1 Generating a Finite Automaton

虽然有限自动机原则上可以手写，但更常见的是使用扫描器生成器工具从一组正则表达式自动构建一个。对于我们的计算器语言，我们希望将示例 2.9中的正则表达式转换为图 2.6中的自动机。该自动机具有理想的属性，即其动作是确定性的：在任何给定状态下，对于给定的输入字符，永远不会有超过一个可能的输出转换（箭头）由该字符标记。然而事实证明，没有明显的一步算法可以将一组正则表达式转换为等效的确定性有限自动机 (DFA)。典型的扫描器生成器将转换作为一系列三个独立的步骤来实现。

While a finite automaton can in principle be written by hand, it is more common to build one automatically from a set of regular expressions, using a scanner generator tool. For our calculator language, we should like to covert the regular expressions of Example 2.9 into the automaton of Figure 2.6. That automaton has the desirable property that its actions are deterministic: in any given state with a given input character there is never more than one possible outgoing transition (arrow) labeled by that character. As it turns out, however, there is no obvious one-step algorithm to convert a set of regular expressions into an equivalent deterministic finite automaton (DFA). The typical scanner generator implements the conversion as a series of three separate steps.

第一步将正则表达式转换为非确定性有限自动机 (NFA)。NFA 与 DFA 类似，不同之处在于 (1) 给定字符标记的给定状态可能存在多个转换，以及 (2) 可能存在所谓的epsilon 转换：箭头用空字符串符号标记，例如。如果存在从起始状态到终止状态的路径，并且该路径的非 epsilon 转换按顺序用标记的字符标记，则称 NFA 接受输入字符串（标记）。

The first step converts the regular expressions into a nondeterministic finite automaton (NFA). An NFA is like a DFA except that (1) there maybe more than one transition out of a given state labeled by a given character, and (2) there may be so-called epsilon transitions: arrows labeled by the empty string symbol, e. The NFA is said to accept an input string (token) if there exists a path from the start state to a final state whose non-epsilon transitions are labeled, in order, by the characters of the token.

为了避免搜索所有可能的路径以找到“有效”的路径，扫描器生成器的第二步是将 NFA 转换为等效的 DFA：一个接受相同语言的自动机，但其中没有 epsilon 转换，并且没有带有多个由相同字符标记的传出转换的状态。第三步是空间优化，生成具有尽可能少的状态数的最终 DFA。

To avoid the need to search all possible paths for one that “works,” the second step of a scanner generator translates the NFA into an equivalent DFA: an automaton that accepts the same language, but in which there are no epsilon transitions, and no states with more than one outgoing transition labeled by the same character. The third step is a space optimization that generates a final DFA with the minimum possible number of states.

从正则表达式到 NFA

From a Regular Expression to an NFA

例 2.12

Example 2.12

为给定的正则表达式构建 NFA

Constructing an NFA for given regular expression

一个由单个字符c组成的平凡正则表达式等价于一个简单的二状态 NFA（实际上是一个 DFA），如图2.7的 (a) 部分所示。类似地，正则表达式ε等价于一个二状态 NFA，其弧标记为ε。从这个基础开始，我们可以使用三个子构造（如图 2.7 的 (b) 到 (d) 部分所示）来构建更大的 NFA 来表示由较小 NFA 表示的正则表达式的连接、交替或 Kleene 闭包。每一步都保留三个不变量：没有进入初始状态的转换，有一个最终状态，并且没有从最终状态出来的转换。这些不变量允许将较小的自动机连接到较大的自动机中，而不会对在何处创建连接产生任何歧义，也不会创建任何意外路径。■

A trivial regular expression consisting of a single character c is equivalent to a simple two-state NFA (in fact, a DFA), illustrated in part (a) of Figure 2.7. Similarly, the regular expression ε is equivalent to a two-state NFA whose arc is labeled by ε. Starting with this base we can use three subconstructions, illustrated in parts (b) through (d) of the same figure, to build larger NFAs to represent the concatenation, alternation, or Kleene closure of the regular expressions represented by smaller NFAs. Each step preserves three invariants: there are no transitions into the initial state, there is a single final state, and there are no transitions out of the final state. These invariants allow smaller automata to be joined into larger ones without any ambiguity about where to create the connections, and without creating any unexpected paths. ■

例 2.13

Example 2.13

d * ( . d | d . ) d *的 DFA

DFA for d*( .d | d. ) d*

为了使这些构造具体化，我们考虑一个小但并不平凡的例子——示例 2.3中的十进制字符串。它们由包含单个小数点的十进制数字字符串组成。由于只有一位数字，因此小数点可以位于开头或结尾：( . d | d . )，其中为简洁起见，我们使用d来表示任何十进制数字。然后可以在开头或结尾添加任意数量的数字：d * ( . d | d . ) d *。从这个正则表达式开始，并使用图 2.7的构造，我们在图 2.8中说明了等效 NFA 的构造。■

To make these constructions concrete, we consider a small but nontrivial example—the decimal strings of Example 2.3. These consist of a string of decimal digits containing a single decimal point. With only one digit, the point can come at the beginning or the end: ( .d | d. ), where for brevity we use d to represent any decimal digit. Arbitrary numbers of digits can then be added at the beginning or the end: d* ( .d | d. ) d*. Starting with this regular expression and using the constructions of Figure 2.7, we illustrate the construction of an equivalent NFA in Figure 2.8. ■

从 NFA 到 DFA

From an NFA to a DFA

例 2.14

Example 2.14

d * (. d | d . ) d *的 DFA

DFA for d* ( .d | d. ) d*

由于无法“猜测”从任何给定状态采取的正确转换，任何实际的 NFA 实现都需要探索所有可能的转换，同时或通过回溯。为了避免这种复杂且耗时的策略，我们可以使用“子集”构造将 NFA 转换为等效的 DFA。关键思想是让 DFA 在读取给定输入后的状态表示 NFA在相同输入上可能达到的状态集。我们使用图 2.8 中的 NFA说明了图2.9中的构造。最初，在它使用任何输入之前，NFA 可能处于状态 1，或者它可能会进行到状态 2、4、5 或 8 的 epsilon 转换。因此，我们为我们的 DFA 创建一个初始状态A来表示这个集合。在输入d时，我们的 NFA 可能会从状态 2 移动到状态 3，或者从状态 8 移动到状态 9。它在这个输入上没有从A中的任何状态进行的其他转换。但是，从状态 3 开始，NFA 可以通过 epsilon 转换到状态 2、4、5 或 8 中的任意一个。因此，我们创建 DFA 状态B，如图所示。

With no way to “guess” the right transition to take from any given state, any practical implementation of an NFA would need to explore all possible transitions, concurrently or via backtracking. To avoid such a complex and time-consuming strategy, we can use a “set of subsets” construction to transform the NFA into an equivalent DFA. The key idea is for the state of the DFA after reading a given input to represent the set of states that the NFA might have reached on the same input. We illustrate the construction in Figure 2.9 using the NFA from Figure 2.8. Initially, before it consumes any input, the NFA maybe in State 1, or it may make epsilon transitions to States 2, 4, 5, or 8. We thus create an initial State A for our DFA to represent this set. On an input of d, our NFA may move from State 2 to State 3, or from State 8 to State 9. It has no other transitions on this input from any of the states in A. From State 3, however, the NFA may make epsilon transitions to any of States 2, 4, 5, or 8. We therefore create DFA State B as shown.

在 上，我们的 NFA 可以从状态 5 移动到状态 6。此输入上没有来自A中任何状态的其他转换，并且没有来自状态 6 的 epsilon 转换。因此，我们创建单例 DFA 状态C ，如图所示。状态A、B或C均未标记为最终，因为没有一个包含原始 NFA 的最终状态。

On a ., our NFA may move from State 5 to State 6. There are no other transitions on this input from any of the states in A, and there are no epsilon transitions out of State 6. We therefore create the singleton DFA State C as shown. None of States A, B, or C is marked as final, because none contains a final state of the original NFA.

回到不断增长的 DFA 的状态B，我们注意到在输入d时，原始 NFA 可能从状态 2 移动到状态 3 ，或者从状态 8 移动到状态 9 。从状态 3 ，它又可能通过 epsilon 转换移动到状态 2、4、5 或 8 。由于这些正是B中已有的状态，因此我们在 DFA 中创建一个自循环。另一方面，给定 . ，原始 NFA 可能从状态 5 移动到状态 6 ，或者从状态 9 移动到状态 10 。从状态 10 ，它又可能通过 epsilon 转换移动到状态 11、12 或 14 。因此，我们创建如图所示的 DFA 状态D，其中 . 转换从B到D。状态D被标记为最终状态，因为它包含原始 NFA 的状态 14 。也就是说，给定输入d . ，存在一条从原始 NFA 的起始状态到终止状态的路径。继续枚举状态集，我们最终创建了另外三个状态集，在图 2.9中标记为E、F和G。与状态D一样，它们都包含原始 NFA 的状态 14，因此被标记为最终状态。■

Returning to State B of the growing DFA, we note that on an input of d the original NFA may move from State 2 to State 3, or from State 8 to State 9. From State 3, in turn, it may move to States 2, 4, 5, or 8 via epsilon transitions. As these are exactly the states already in B, we create a self-loop in the DFA. Given a ., on the other hand, the original NFA may move from State 5 to State 6, or from State 9 to State 10. From State 10, in turn, it may move to States 11, 12, or 14 via epsilon transitions. We therefore create DFA State D as shown, with a transition on . from B to D. State D is marked as final because it contains state 14 of the original NFA. That is, given input d., there exists a path from the start state to the end state of the original NFA. Continuing our enumeration of state sets, we end up creating three more, labeled E, F, and G in Figure 2.9. Like State D, these all contain State 14 of the original NFA, and thus are marked as final. ■

在我们的示例中，DFA 最终比 NFA 小，但这只是因为我们的常规语言非常简单。理论上，DFA 中的状态数可能是 NFA 中状态数的指数，但这种极端情况在实践中也不常见。对于编程语言扫描器，DFA 往往比 NFA 大，但并不离谱。我们将在 C-2.4.1 节中更详细地考虑空间复杂性。

In our example, the DFA ends up being smaller than the NFA, but this is only because our regular language is so simple. In theory, the number of states in the DFA may be exponential in the number of states in the NFA, but this extreme is also uncommon in practice. For a programming language scanner, the DFA tends to be larger than the NFA, but not outlandishly so. We consider space complexity in more detail in Section C-2.4.1.

最小化 DFA

Minimizing the DFA

例 2.15

Example 2.15

d *( . d | d . ) d *的最小 DFA

Minimal DFA for d*( .d | d. ) d*

从正则表达式开始，我们现在构建了一个等效的 DFA。虽然这个 DFA 有七个状态，但经过一番思考，我们发现应该存在一个更小的状态。特别是，一旦我们看到 d和.，唯一有效的转换就在d上，我们应该能够使用单个最终状态。我们可以通过以下归纳构造将这种直觉形式化，从而将其应用于任何 DFA。

Starting from a regular expression, we have now constructed an equivalent DFA. Though this DFA has seven states, a bit of thought suggests that a smaller one should exist. In particular, once we have seen both a d and a ., the only valid transitions are on d, and we ought to be able to make do with a single final state. We can formalize this intuition, allowing us to apply it to any DFA, via the following inductive construction.

最初，我们将（不一定是最小的）DFA 的状态放入两个等价类：最终状态和非最终状态。然后，我们反复搜索等价类κ和输入符号c，使得当给定c作为输入时， κ中的状态会转换为k > 1 个不同等价类中的状态。然后，我们将κ划分为k个类，使得给定新类中的所有状态都会移动到c上的同一旧类的成员。当我们无法找到以这种方式划分的类时，我们就完成了。

Initially we place the states of the (not necessarily minimal) DFA into two equivalence classes: final states and nonfinal states. We then repeatedly search for an equivalence class κ and an input symbol c such that when given c as input, the states in κ make transitions to states in k > 1 different equivalence classes. We then partition κ into k classes in such a way that all states in a given new class would move to a member of the same old class on c. When we are unable to find a class to partition in this fashion we are done.

在我们的例子中，原来的放置方式是将状态D 、 E 、 F和G放在一个类 (最终状态) 中，而将状态A、B和C放在另一个类中，如图2.10的左上角所示。不幸的是，起始状态在d和 . 上都有歧义转换。为了解决d 的歧义，我们将ABC拆分为AB和C，如右上角所示。新状态AB在d上有一个自循环；新状态C移动到状态DEFG。但是，状态AB在 . 上仍然有歧义，我们通过将其拆分为状态A和B来解决此问题，如图底部所示。此时没有进一步的歧义，我们剩下四状态最小 DFA。■

In our example, the original placement puts States D, E, F, and G in one class (final states) and States A, B, and C in another, as shown in the upper left of Figure 2.10. Unfortunately, the start state has ambiguous transitions on both d and .. To address the d ambiguity, we split ABC into AB and C, as shown in the upper right. New State AB has a self-loop on d; new State C moves to State DEFG. State AB still has an ambiguity on ., however, which we resolve by splitting it into States A and B, as shown at the bottom of the figure. At this point there are no further ambiguities, and we are left with a four-state minimal DFA. ■

2.2.2 扫描器代码

2.2.2 Scanner Code

我们可以通过两种主要方式中的任一种实现一个扫描器，以明确捕获 DFA 的“圆圈和箭头”结构。一种方式是使用goto或嵌套case (switch)语句将自动机嵌入到程序的控制流中；另一种方式（如下一小节所述）使用表和驱动程序。一般来说，手写自动机倾向于使用嵌套 case 语句，而大多数自动生成的自动机使用表。表很难手动创建，但比在程序内部创建代码更容易。同样，嵌套 case 语句比图 2.5中的临时方法更容易编写和调试，尽管效率不如图 2.5 那么高。Unix 的lex/flex工具生成包含表和自定义驱动程序的 C 语言输出。

We can implement a scanner that explicitly captures the “circles-and-arrows” structure of a DFA in either of two main ways. One embeds the automaton in the control flow of the program using gotos or nested case (switch) statements; the other, described in the following subsection, uses a table and a driver. As a general rule, handwritten automata tend to use nested case statements, while most automatically generated automata use tables. Tables are hard to create by hand, but easier than code to create from within a program. Likewise, nested case statements are easier to write and to debug than the ad hoc approach of Figure 2.5, if not quite as efficient. Unix's lex/flex tool produces C language output containing tables and a customized driver.

例 2.16

Example 2.16

嵌套case语句自动化

Nested case statement automation

嵌套 case 语句风格的自动机具有以下一般结构：

The nested case statement style of automaton has the following general structure:

state := 1 –– 起始状态

state := 1 –– start state

环形

loop

 读取当前字符

 read cur char

 案件状态

 case state of

  1：案例 cur_char

  1 : case cur_char of

   ' ', '\t', '\n' : …

   ‘ ’, ‘\t’, ‘\n’ : …

   ‘a’…‘z’：…

   ‘a’… ‘z’ : …

   '0'…'9'：...

   ‘0’… ‘9’ : …

   '>' ：…

   ‘>’ : …

   …

   …

  2：案例 cur_char

  2 : case cur_char of

   …

   …

   …

   …

  n： 案例 cur_char

  n: case cur_char of

   …

   …

外部case语句涵盖有限自动机的状态。内部case语句涵盖每个状态的转换。大多数内部子句只是设置一个新状态。有些从扫描器返回当前标记。（如果当前字符不应该是该标记的一部分，它将被推回到输入流然后再返回。）■

The outer case statement covers the states of the finite automaton. The inner case statements cover the transitions out of each state. Most of the inner clauses simply set a new state. Some return from the scanner with the current token. (If the current character should not be part of that token, it is pushed back onto the input stream before returning.) ■

代码的两个方面通常与形式有限自动机的严格形式不同。一个是关键字的处理。另一个是需要提前预知何时标记可以有效地扩展两个或更多个附加字符，但不能只扩展一个。

Two aspects of the code typically deviate from the strict form of a formal finite automaton. One is the handling of keywords. The other is the need to peek ahead when a token can validly be extended by two or more additional characters, but not by only one.

如第 2.1.1 节开头所述，大多数语言中的关键字看起来就像标识符，但保留用于特殊用途（一些作者使用术语“保留字”而不是“关键字”）。可以编写一个区分关键字和标识符的有限自动机，但它需要很多状态（参见练习 2.3）。因此，大多数扫描器（无论是手写还是自动生成的）都将关键字视为标识符规则的“例外”。在返回之前解析器的标识符，扫描器会在哈希表或 trie（分支路径树）中查找它，以确保它不是真正的关键字^。10

As noted at the beginning of Section 2.1.1, keywords in most languages look just like identifiers, but are reserved for a special purpose (some authors use the term reserved word instead of keyword). It is possible to write a finite automaton that distinguishes between keywords and identifiers, but it requires a lot of states (see Exercise 2.3). Most scanners, both handwritten and automatically generated, therefore treat keywords as “exceptions” to the rule for identifiers. Before returning an identifier to the parser, the scanner looks it up in a hash table or trie (a tree of branching paths) to make sure it isn't really a keyword.¹⁰

设计与实现

Design & Implementation

2.4 识别多种 token

2.4 Recognizing multiple kinds of token

扫描器与正式 DFA 的主要区别之一是，它除了识别标记之外，还识别标记。也就是说，它不仅确定字符是否构成有效标记；它还指示哪一个。实际上，这意味着它必须为每种标记设置单独的最终状态。我们在 RE-to-DFA 构造中略过了这个问题。

One of the chief ways in which a scanner differs from a formal DFA is that it identifies tokens in addition to recognizing them. That is, it not only determines whether characters constitute a valid token; it also indicates which one. In practice, this means that it must have separate final states for every kind of token. We glossed over this issue in our RE-to-DFA constructions.

要为具有n种不同标记的语言构建扫描器，我们从此处图中建议的 NFA 开始。给定 NFA M _i，1 ≤ i ≤ n（每种标记一个自动机），我们创建一个新的起始状态，其中 epsilon 转换到M _i的起始状态。但是，与图 2.7(c)中的交替构造相反，我们不会创建单个最终状态；我们保留现有的状态，每个状态都标有其最终标记的标记。然后我们像以前一样应用 NFA-to-DFA 构造。（如果 NFA 中不同标记的最终状态最终处于 DFA 的相同状态，则我们有不明确的标记定义。这些问题可以通过更改派生 NFA 的正则表达式或在 DFA 周围包装其他逻辑来解决。）

To build a scanner for a language with n different kinds of tokens, we begin with an NFA of the sort suggested in the figure here. Given NFAs M_i, 1 ≤ i ≤ n (one automaton for each kind of token), we create a new start state with epsilon transitions to the start states of the M_is. In contrast to the alternation construction of Figure 2.7(c), however, we do not create a single final state; we keep the existing ones, each labeled by the token for which it is final. We then apply the NFA-to-DFA construction as before. (If final states for different tokens in the NFA ever end up in the same state of the DFA, then we have ambiguous token definitions. These may be resolved by changing the regular expressions from which the NFAs were derived, or by wrapping additional logic around the DFA.)

在 DFA 最小化构造中，我们不是从两个等价类（最终状态和非最终状态）开始，而是从n + 1 开始，包括每种标记类型的最终状态的单独类。练习 2.5探索了这种构造，用于识别示例 2.3中的整数和小数类型的扫描仪。

In the DFA minimization construction, instead of starting with two equivalence classes (final and nonfinal states), we begin with n + 1, including a separate class for final states for each of the kinds of token. Exercise 2.5 explores this construction for a scanner that recognizes both the integer and decimal types of Example 2.3.

例 2.17

Example 2.17

非平凡前缀问题

The nontrivial prefix problem

每当一个合法标记是另一个标记的前缀时，“最长标记”规则就表明我们应该继续扫描。但是，如果某些中间字符串不是有效标记，我们无法判断是否有可能出现更长的标记，除非我们向前查看多个字符。这个问题出现在 C 中的点字符（句点）上。假设扫描器刚刚看到 3，并且输入中有一个点。它需要查看点以外的字符，以区分3.14（表示实数的单个标记）、3 . foo（扫描器应该接受的三个标记，即使解析器反对按该顺序查看它们）和3 … foo（同样在语法上无效，但仍然是三个独立的标记）。通常，扫描器必须检查以做出决定的即将到来的字符称为其前瞻。在第 2.3 节中，我们将在解析中看到类似的前瞻标记概念。■

Whenever one legitimate token is a prefix of another, the “longest possible token” rule says that we should continue scanning. If some of the intermediate strings are not valid tokens, however, we can't tell whether a longer token is possible without looking more than one character ahead. This problem arises with dot characters (periods) in C. Suppose the scanner has just seen a 3 and has a dot coming up in the input. It needs to peek at characters beyond the dot in order to distinguish between 3.14 (a single token designating a real number), 3 . foo (three tokens that the scanner should accept, even though the parser will object to seeing them in that order), and 3 … foo (again not syntactically valid, but three separate tokens nonetheless). In general, upcoming characters that a scanner must examine in order to make a decision are known as its look-ahead. In Section 2.3 we will see a similar notion of look-ahead tokens in parsing. ■

例 2.18

Example 2.18

Fortran 扫描中的前瞻

Look-ahead in Fortran scanning

在较为复杂的语言中，扫描器可能需要提前任意距离查看。例如，在 Fortran IV 中，DO 5 I = 1,25是循环的标题（对于I的值从 1 到25 ，它执行直到标号为5的语句），而DO 5 I = 1.25是一条赋值语句，它将值1.25放入变量DO5I中。在（Fortran 90 之前的版本）Fortran 输入中会忽略空格，即使在变量名中间也是如此。此外，变量无需声明，DO循环的终止符只是一个标签，解析器可以忽略它。看到DO之后，扫描器无法判断5是否是当前标记的一部分，直到它到达逗号或点。人们普遍（但显然是错误的）声称 NASA 的水手 1 号太空探测器丢失是因为意外将逗号替换为点，飞行控制软件中的情况与此类似。从 Fortran 77 开始的¹¹种 Fortran 方言允许（实际上鼓励）使用替代循环头的语法，其中额外的逗号可以减少误解的可能性：DO 5,I = 1,25。■

In messier languages, a scanner may need to look an arbitrary distance ahead. In Fortran IV, for example, DO 5 I = 1,25 is the header of a loop (it executes the statements up to the one labeled 5 for values of I from 1 to 25), while DO 5 I = 1.25 is an assignment statement that places the value 1.25 into the variable DO5I. Spaces are ignored in (pre-Fortran 90) Fortran input, even in the middle of variable names. Moreover, variables need not be declared, and the terminator for a DO loop is simply a label, which the parser can ignore. After seeing DO, the scanner cannot tell whether the 5 is part of the current token until it reaches the comma or dot. It has been widely (but apparently incorrectly) claimed that NASA's Mariner 1 space probe was lost due to accidental replacement of a comma with a dot in a case similar to this one in flight control software.¹¹ Dialects of Fortran starting with Fortran 77 allow (in fact encourage) the use of alternative syntax for loop headers, in which an extra comma makes misinterpretation less likely: DO 5,I = 1,25. ■

设计与实现

Design & Implementation

2.5 最长可能的标记

2.5 Longest possible tokens

在语法设计中稍加注意（避免使用其他标记的非平凡前缀的标记）可以大大简化扫描。在前缀歧义的简单情况下，扫描器可以自动执行“最长可能的标记”规则。然而，在 Fortran 中，规则非常复杂，以至于没有纯粹的词汇解决方案可以满足需要。Dyadkin 的一篇文章 [ Dya95 ] 讨论了其中一些问题以及可能的解决方案。

A little care in syntax design—avoiding tokens that are nontrivial prefixes of other tokens—can dramatically simplify scanning. In straightforward cases of prefix ambiguity, the scanner can enforce the “longest possible token” rule automatically. In Fortran, however, the rules are sufficiently complex that no purely lexical solution suffices. Some of the problems, and a possible solution, are discussed in an article by Dyadkin [Dya95].

在 C 语言中，点字符问题可以很容易地作为特殊情况处理。在需要大量前瞻的语言中，扫描器可以采用更通用的方法。在任何歧义情况下，它都假设可以使用较长的标记，但会记住较短的标记可能在过去的某个时间点被识别。它还会缓冲较短标记末尾之后读取的所有字符。如果乐观的假设导致扫描器进入错误状态，它会“取消读取”缓冲的字符，以便稍后再次看到它们，并返回较短的标记。

In C, the dot character problem can easily be handled as a special case. In languages requiring larger amounts of look-ahead, the scanner can take a more general approach. In any case of ambiguity, it assumes that a longer token will be possible, but remembers that a shorter token could have been recognized at some point in the past. It also buffers all characters read beyond the end of the shorter token. If the optimistic assumption leads the scanner into an error state, it “unreads” the buffered characters so that they will be seen again later, and returns the shorter token.

2.2.3 表驱动扫描

2.2.3 Table-Driven Scanning

例 2.19

Example 2.19

表格驱动扫描

Table-driven scanning

在前面的小节中，我们概述了如何使用控制流（循环和嵌套的 case 语句）来表示有限自动机。 另一种方法是将自动机表示为一种数据结构：二维转换表。 驱动程序（图 2.11）使用当前状态和输入字符作为该表的索引。 表中的每个条目指定是否移动到新状态（如果是，则移动到哪一个状态）、返回标记还是宣布错误。 第二个表指示对于每个状态我们是否可能位于标记的末尾（如果是，则位于哪一个）。 将第二个表与第一个表分开可以让我们注意到何时经过可能是标记末尾的状态，因此如果遇到错误状态，我们可以后退。图 2.12显示了我们的计算器标记的示例表。

In the preceding subsection we sketched how control flow—a loop and nested case statements—can be used to represent a finite automaton. An alternative approach represents the automaton as a data structure: a two-dimensional transition table. A driver program (Figure 2.11) uses the current state and input character to index into the table. Each entry in the table specifies whether to move to a new state (and if so, which one), return a token, or announce an error. A second table indicates, for each state, whether we might be at the end of a token (and if so, which one). Separating this second table from the first allows us to notice when we pass a state that might have been the end of a token, so we can back up if we hit an error state. Example tables for our calculator tokens appear in Figure 2.12.

就像手写扫描仪一样，图 2.11中的表格驱动代码在返回之前立即在关键字表中查找标记。外循环用于过滤掉注释和“空白”——空格、制表符和换行符。■

Like a handwritten scanner, the table-driven code of Figure 2.11 looks tokens up in a table of keywords immediately before returning. An outer loop serves to filter out comments and “white space”—spaces, tabs, and newlines. ■

2.3 解析

2.3 Parsing

解析器是典型编译器的核心。它调用扫描器来获取输入程序的标记，将标记组合成语法树，并将该树（可能一次一个子例程）传递给编译器的后续阶段，执行语义分析和代码生成和改进。实际上，解析器“负责”整个编译过程；这种编译风格有时被称为语法制导翻译。

The parser is the heart of a typical compiler. It calls the scanner to obtain the tokens of the input program, assembles the tokens together into a syntax tree, and passes the tree (perhaps one subroutine at a time) to the later phases of the compiler, which perform semantic analysis and code generation and improvement. In effect, the parser is “in charge” of the entire compilation process; this style of compilation is sometimes referred to as syntax-directed translation.

如本章简介中所述，上下文无关文法 (CFG) 是CF 语言的生成器。解析器是一种语言识别器。可以证明，对于任何 CFG，我们都可以创建一个运行时间为O ( n3 ) 的解析器，其中n是输入程序的长度。12^有两种著名的解析算法可以达到这个界限：Earley 算法 [ Ear70 ] 和 Cocke-Younger-Kasami (CYK) 算法 [ Kas65、You67 ]。^立方时间对于解析大型程序来说太慢了，但幸运的是，并非所有语法都需要这种通用且缓慢的解析算法。我们可以为很多类语法构建以线性时间运行的解析器。其中最重要的两个类称为 LL 和 LR（图 2.13）。

As noted in the introduction to this chapter, a context-free grammar (CFG) is a generator for a CF language. A parser is a language recognizer. It can be shown that for any CFG we can create a parser that runs in O(n³) time, where n is the length of the input program.¹² There are two well-known parsing algorithms that achieve this bound: Earley's algorithm [Ear70] and the Cocke-Younger-Kasami (CYK) algorithm [Kas65, You67]. Cubic time is much too slow for parsing sizable programs, but fortunately not all grammars require such a general and slow parsing algorithm. There are large classes of grammars for which we can build parsers that run in linear time. The two most important of these classes are called LL and LR (Figure 2.13).

LL 代表“从左到右，最左派生”。LR 代表“从左到右，最右派生”。在这两个类中，输入都是从左到右读取的，并且解析器尝试发现（构造）该输入的派生。对于 LL 解析器，派生将是最左边的；对于 LR 解析器，派生将是最右边的。我们将首先介绍 LL 解析器。它们通常被认为更简单且更容易理解。它们可以手写，也可以由解析器生成工具从适当的语法自动生成。LR 语法类更大（即，LR 语法比 LL 语法更多），有些人发现 LR 语法的结构更直观，尤其是在处理算术表达式时。LR 解析器几乎总是由解析器生成工具构建。这两类解析器都用于生产编译器，尽管 LR 解析器更常见。

LL stands for “Left-to-right, Left-most derivation.” LR stands for “Left-to-right, Right-most derivation.” In both classes the input is read left-to-right, and the parser attempts to discover (construct) a derivation of that input. For LL parsers, the derivation will be left-most; for LR parsers, right-most. We will cover LL parsers first. They are generally considered to be simpler and easier to understand. They can be written by hand or generated automatically from an appropriate grammar by a parser-generating tool. The class of LR grammars is larger (i.e., more grammars are LR than LL), and some people find the structure of the LR grammars more intuitive, especially in the handling of arithmetic expressions. LR parsers are almost always constructed by a parser-generating tool. Both classes of parsers are used in production compilers, though LR parsers are more common.

LL 解析器也称为“自上而下”或“预测”解析器。它们从根部向下构建解析树，在每个步骤中根据下一个可用的输入标记预测将使用哪个生成式来扩展当前节点。LR 解析器也称为“自下而上”解析器。它们从叶子向上构建解析树，识别何时可以将一组叶子或其他节点连接在一起作为单个父节点的子节点。

LL parsers are also called “top-down,” or “predictive” parsers. They construct a parse tree from the root down, predicting at each step which production will be used to expand the current node, based on the next available token of input. LR parsers are also called “bottom-up” parsers. They construct a parse tree from the leaves up, recognizing when a collection of leaves or other nodes can be joined together as the children of a single parent.

例 2.20

Example 2.20

自上而下和自下而上的解析

Top-down and bottom-up parsing

我们可以通过一个简单的例子来说明自上而下和自下而上解析之间的区别。考虑以下以逗号分隔的标识符列表的语法，以分号结尾：

We can illustrate the difference between top-down and bottom-up parsing by means of a simple example. Consider the following grammar for a comma-separated list of identifiers, terminated by a semicolon:

id_list → id id_list_tail

id_list → id id_list_tail

id_list_tail →，id id_list_tail

id_list_tail →, id id_list_tail

id_列表_尾部→；

id_list_tail → ;

这些是通常用于自上而下解析器中的标识符列表的产生式。它们也可以自下而上地解析（大多数自上而下的语法都可以）。实际上，它们不会在自下而上的解析器中使用，原因稍后会清楚，但能够以任何一种方式处理它们使它们非常适合此示例。

These are the productions that would normally be used for an identifier list in a top-down parser. They can also be parsed bottom-up (most top-down grammars can be). In practice they would not be used in a bottom-up parser, for reasons that will become clear in a moment, but the ability to handle them either way makes them good for this example.

图 2.14显示了自上而下和自下而上构建字符串A，B，C；的解析树的渐进阶段。自上而下的解析器首先预测树的根（id_list）将扩展为id id_list_tail。然后将 id 与从扫描器获取的标记进行匹配。（如果扫描器生成了不同的结果，解析器将宣布语法错误。）然后，解析器向下移动到第一个（在本例中仅此一个）非终结子节点，并预测 id_list_tail将扩展为id id_list_tail。为了做出这个预测，它需要查看即将到来的标记（逗号），这使它能够在id_list_tail的两种可能扩展之间进行选择。然后，它匹配逗号和id，并向下移动到下一个id_list_tail。以类似的递归方式，自上而下的解析器沿着树从左到右进行工作，预测和扩展节点并追踪树边缘最左边的派生。

Progressive stages in the top-down and bottom-up construction of a parse tree for the string A, B, C; appear in Figure 2.14. The top-down parser begins by predicting that the root of the tree (id_list) will expand to id id_list_tail. It then matches the id against a token obtained from the scanner. (If the scanner produced something different, the parser would announce a syntax error.) The parser then moves down into the first (in this case only) nonterminal child and predicts that id_list_tail will expand to, id id_list_tail. To make this prediction it needs to peek at the upcoming token (a comma), which allows it to choose between the two possible expansions for id_list_tail. It then matches the comma and the id and moves down into the next id_list_tail. In a similar, recursive fashion, the top-down parser works down the tree, left-to-right, predicting and expanding nodes and tracing out a left-most derivation of the fringe of the tree.

相比之下，自下而上的解析器首先注意到树的最左边的叶子是一个id。下一个叶子是一个逗号，再下一个叶子是另一个id。解析器以这种方式继续，将新的叶子从扫描器移到部分完成的解析树片段的森林中，直到它意识到其中一些片段构成了一个完整的右侧。在这个语法中，直到解析器看到分号（id_list_tail → ; 的右侧）时才会发生这种情况。有了这个右侧，解析器将分号简化为id_list_tail。然后它将id id_list_tail简化为另一个id_list_tail。再做一次之后，它就能够将id id_list_tail简化为解析树的根id_list。

The bottom-up parser, by contrast, begins by noting that the left-most leaf of the tree is an id. The next leaf is a comma and the one after that is another id. The parser continues in this fashion, shifting new leaves from the scanner into a forest of partially completed parse tree fragments, until it realizes that some of those fragments constitute a complete right-hand side. In this grammar, that doesn't occur until the parser has seen the semicolon—the right-hand side of id_list_tail → ;. With this right-hand side in hand, the parser reduces the semicolon to an id_list_tail. It then reduces, id id_list_tail into another id_list_tail. After doing this one more time it is able to reduce id id_list_tail into the root of the parse tree, id_list.

自下而上的解析器从来不会预测接下来会看到什么。相反，它会将标记移入其森林，直到识别出右侧，然后将其归约到左侧。由于这种行为，自下而上的解析器有时被称为移位归约解析器。从下往上移动图片，我们可以看到移位归约解析器反向追踪最右侧的推导。由于自下而上的解析器是第一个得到仔细正式研究的解析器，因此最右侧的推导有时被称为规范的。■

At no point does the bottom-up parser predict what it will see next. Rather, it shifts tokens into its forest until it recognizes a right-hand side, which it then reduces to a left-hand side. Because of this behavior, bottom-up parsers are sometimes called shift-reduce parsers. Moving up the figure, from bottom to top, we can see that the shift-reduce parser traces out a right-most derivation, in reverse. Because bottom-up parsers were the first to receive careful formal study, right-most derivations are sometimes called canonical. ■

LR 解析器有几个重要的子类，包括 SLR、LALR 和“完整 LR”。SLR 和 LALR 因其易于实现而重要，而完整 LR 因其通用性而重要。LL 解析器也可以分为 SLL 和“完整 LL”子类。我们在此仅简要介绍它们之间的差异；有关更多信息，请参阅任何标准编译器构造或解析理论教科书 [ App97、ALSU07、AU72、CT04、FCL10、GBJ ⁺ 12 ]。

There are several important subclasses of LR parsers, including SLR, LALR, and “full LR.” SLR and LALR are important for their ease of implementation, full LR for its generality. LL parsers can also be grouped into SLL and “full LL” subclasses. We will cover the differences among them only briefly here; for further information see any of the standard compiler-construction or parsing theory textbooks [App97, ALSU07, AU72, CT04, FCL10, GBJ⁺12].

我们通常看到 LL 或 LR（或其他名称）后面带有括号中的数字：例如 LL(2) 或 LALR(1)。此数字表示解析需要多少个前瞻标记。大多数实际编译器只使用一个前瞻标记，但有时使用更多标记会有所帮助。特别是，开源工具 ANTLR 使用多标记前瞻来扩大适合自上而下解析的语言类 [ PQ95 ]。在第 2.3.1 节中，我们将更详细地介绍 LL(1) 语法和手写解析器。在第 2.3.3 节和2.3.4节中，我们将考虑自动生成的 LL(1) 和 LR(1)（实际上是 SLR(1)）解析器。

One commonly sees LL or LR (or whatever) written with a number in parentheses after it: LL(2) or LALR(1), for example. This number indicates how many tokens of look-ahead are required in order to parse. Most real compilers use just one token of look-ahead, though more can sometimes be helpful. The open-source ANTLR tool, in particular, uses multitoken look-ahead to enlarge the class of languages amenable to top-down parsing [PQ95]. In Section 2.3.1 we will look at LL(1) grammars and handwritten parsers in more detail. In Sections 2.3.3 and 2.3.4 we will consider automatically generated LL(1) and LR(1) (actually SLR(1)) parsers.

例 2.21

Example 2.21

使用自下而上的语法来限制空间

Bounding space with a bottom-up grammar

对于自下而上的解析来说，我们的示例语法存在一个问题，即它迫使编译器将id_list的所有标记移入其森林，然后才能减少其中任何一个。在一个非常大的程序中，我们可能会用尽空间。有时没有什么可以避免大量移位。然而，在这种情况下，我们可以使用另一种语法，允许解析器在解析过程中将id_list的前缀减少为非终结符：

The problem with our example grammar, for the purposes ofbottom-up parsing, is that it forces the compiler to shift all the tokens of an id_list into its forest before it can reduce any of them. In a very large program we might run out of space. Sometimes there is nothing that can be done to avoid a lot of shifting. In this case, however, we can use an alternative grammar that allows the parser to reduce prefixes of the id_list into nonterminals as it goes along:

id_列表→ id_列表前缀；

id_list → id_list_prefix ;

id_列表_前缀→ id_列表_前缀, id

id_list_prefix → id_list_prefix, id

 → id

 → id

此语法无法自上而下解析，因为当我们在输入中看到id并且我们期望id_list_prefix时，我们无法分辨应该预测两种可能产生式中的哪一种（有关此困境的更多信息，请参阅第 2.3.2 节）。但是，如图2.15所示，此语法自下而上运行良好。■

This grammar cannot be parsed top-down, because when we see an id on the input and we're expecting an id_list_prefix, we have no way to tell which of the two possible productions we should predict (more on this dilemma in Section 2.3.2). As shown in Figure 2.15, however, the grammar works well bottom-up. ■

2.3.1 递归下降

2.3.1 Recursive Descent

例 2.22

Example 2.22

自上而下的计算器语言语法

Top-down grammar for a calculator language

为了说明自上而下（预测）解析，我们考虑一下简单“计算器”语言的文法，如图2.16所示。计算器允许将值读入命名变量，然后可在表达式中使用。表达式反过来可以写入输出。控制流是严格线性的（没有循环、if语句或其他跳转）。在我们的许多示例中都会重复出现的一种模式是，我们包括一个初始扩充产生式，program → stmt_list $$，它安排程序的“实际”主体（stmt_list）后面跟着一个特殊的结束标记$$ 。结束标记由扫描器在输入末尾生成。它的存在允许解析器在看到整个程序后干净地终止，并拒绝接受末尾带有额外垃圾标记的程序。与正则表达式一样，我们使用符号ε表示空字符串。右侧带有ε的产生式有时称为epsilon 产生式。

To illustrate top-down (predictive) parsing, let us consider the grammar for a simple “calculator” language, shown in Figure 2.16. The calculator allows values to be read into named variables, which may then be used in expressions. Expressions in turn maybe written to the output. Control flow is strictly linear (no loops, if statements, or other jumps). In a pattern that will repeat in many of our examples, we have included an initial augmenting production, program → stmt_list $$, which arranges for the “real” body of the program (stmt_list) to be followed by a special end marker token, $$. The end marker is produced by the scanner at the end of the input. Its presence allows the parser to terminate cleanly once it has seen the entire program, and to decline to accept programs with extra garbage tokens at the end. As in regular expressions, we use the symbol ε to denote the empty string. A production with ε on the right-hand side is sometimes called an epsilon production.

将图 2.16的expr部分与示例 2.8的表达式语法进行比较可能会有所帮助。大多数人发现以前的 LR 语法更加直观。然而，它存在与示例 2.21的id_list语法类似的问题：如果我们在期望expr时在输入中看到id，我们就无法分辨应该预测两个可能的产生式中的哪一个。图 2.16的语法通过将右侧的公共前缀合并为一个产生式，并使用新符号（term_tail和factor_tail）根据需要生成其他运算符和操作数来避免这个问题。这种转换有一个不良的副作用，即将给定运算符的操作数放在单独的右侧。实际上，我们牺牲了语法的优雅性，以便能够进行预测性解析。■

It may be helpful to compare the expr portion of Figure 2.16 to the expression grammar of Example 2.8. Most people find that previous, LR grammar to be significantly more intuitive. It suffers, however, from a problem similar to that of the id_list grammar of Example 2.21: if we see an id on the input when expecting an expr, we have no way to tell which of the two possible productions to predict. The grammar of Figure 2.16 avoids this problem by merging the common prefixes of right-hand sides into a single production, and by using new symbols (term_tail and factor_tail) to generate additional operators and operands as required. The transformation has the unfortunate side effect of placing the operands of a given operator in separate right-hand sides. In effect, we have sacrificed grammatical elegance in order to be able to parse predictively. ■

那么，我们如何使用计算器语法来解析字符串呢？我们在图 2.14中看到了基本思想。我们从树的顶部开始，根据树中当前最左边的非终结符和当前输入标记预测所需的产生式。我们可以通过两种方式之一来形式化此过程。第一种方法（本小节的其余部分将介绍）是构建一个递归下降解析器，其子例程与语法的非终结符一一对应。递归下降解析器通常是手工构建的，尽管 ANTLR 解析器生成器会根据输入语法自动构建它们。第二种方法（第2.3.3 节中介绍）是构建一个LL 解析表，然后由驱动程序读取。表驱动解析器几乎总是由解析器生成器自动构建。这两个选项（递归下降和表驱动）让人想起嵌套的case语句和表驱动方法构建我们在2.2.2和2.2.3节中看到的扫描器。需要强调的是，它们实现了相同的基本解析算法。

So how do we parse a string with our calculator grammar? We saw the basic idea in Figure 2.14. We start at the top of the tree and predict needed productions on the basis of the current left-most nonterminal in the tree and the current input token. We can formalize this process in one of two ways. The first, described in the remainder of this subsection, is to build a recursive descent parser whose subroutines correspond, one-one, to the nonterminals of the grammar. Recursive descent parsers are typically constructed by hand, though the ANTLR parser generator constructs them automatically from an input grammar. The second approach, described in Section 2.3.3, is to build an LL parse table which is then read by a driver program. Table-driven parsers are almost always constructed automatically by a parser generator. These two options—recursive descent and table-driven—are reminiscent of the nested case statements and table-driven approaches to building a scanner that we saw in Sections 2.2.2 and 2.2.3. It should be emphasized that they implement the same basic parsing algorithm.

当要解析的语言相对简单，或者没有可用的解析器生成器工具时，最常使用手写递归下降解析器。但是也有例外。特别是，递归下降出现在 GNU 编译器集合 ( gcc ) 的最新版本中。早期版本使用bison自动创建自下而上的解析器。进行此更改部分是出于性能原因，部分是为了能够生成更高质量的语法错误消息。（bison代码更容易编写，而且可以说更易于维护。）

Handwritten recursive descent parsers are most often used when the language to be parsed is relatively simple, or when a parser-generator tool is not available. There are exceptions, however. In particular, recursive descent appears in recent versions of the GNU compiler collection (gcc). Earlier versions used bison to create a bottom-up parser automatically. The change was made in part for performance reasons and in part to enable the generation of higher-quality syntax error messages. (The bison code was easier to write, and arguably easier to maintain.)

例 2.23

Example 2.23

计算器语言的递归下降解析器

Recursive descent parser for the calculator language

图 2.17给出了我们的计算器语言的递归下降解析器的伪代码。它对语法中的每个非终结符都有一个子例程。它还有一个机制input_token来检查扫描器提供的下一个可用标记，以及一个子例程 ( match ) 来使用和更新此标记，并在此过程中验证它是否是预期的标记（由参数指定）。如果match或任何其他子例程看到意外标记，则发生语法错误。暂时让我们假设parse_error子例程只是打印一条消息并终止解析。在第 2.3.5 节中，我们将考虑如何从此类错误中恢复并继续解析输入的其余部分。■

Pseudocode for a recursive descent parser for our calculator language appears in Figure 2.17. It has a subroutine for every nonterminal in the grammar. It also has a mechanism input_token to inspect the next token available from the scanner and a subroutine (match) to consume and update this token, and in the process verify that it is the one that was expected (as specified by an argument). If match or any of the other subroutines sees an unexpected token, then a syntax error has occurred. For the time being let us assume that the parse_error subroutine simply prints a message and terminates the parse. In Section 2.3.5 we will consider how to recover from such errors and continue to parse the remainder of the input. ■

例 2.24

Example 2.24

“求和与平均”程序的递归下降解析

Recursive descent parse of a “sum and average” program

现在假设我们要解析一个简单的程序来读取两个数字并打印它们的总和和平均值：

Suppose now that we are to parse a simple program to read two numbers and print their sum and average:

读A

read A

读B

read B

总和 := A + B

sum := A + B

写总和

write sum

写出总和 / 2

write sum / 2

该程序的解析树如图2.18所示。解析器首先调用子程序program。在注意到初始标记是read之后，program调用stmt_list，然后尝试匹配文件结束伪标记。（在解析树中，根program有两个子节点，stmt_list和$$。）过程stmt_list再次注意到即将到来的标记是read。这一观察使其能够确定当前节点（stmt_list）生成stmt stmt_list（而不是ε）。因此，它在返回之前调用stmt和stmt_list。以此方式继续，解析器的执行路径描绘出从左到右的深度优先遍历解析树。动态执行跟踪和解析树结构之间的这种对应关系是递归下降解析的显著特征。注意，因为stmt_list非终结符出现在stmt_list产生式的右侧，所以stmt_list子例程必须调用自身。此递归解释了解析技术的名称。■

The parse tree for this program appears in Figure 2.18. The parser begins by calling the subroutine program. After noting that the initial token is a read, program calls stmt_list and then attempts to match the end-of-file pseudotoken. (In the parse tree, the root, program, has two children, stmt_list and $$.) Procedure stmt_list again notes that the upcoming token is a read. This observation allows it to determine that the current node (stmt_list) generates stmt stmt_list (rather than ε). It therefore calls stmt and stmt_list before returning. Continuing in this fashion, the execution path of the parser traces out a left-to-right depth-first traversal of the parse tree. This correspondence between the dynamic execution trace and the structure of the parse tree is the distinguishing characteristic of recursive descent parsing. Note that because the stmt_list nonterminal appears in the right-hand side of a stmt_list production, the stmt_list subroutine must call itself. This recursion accounts for the name of the parsing technique. ■

如果没有附加代码（图 2.17中未显示），解析器仅验证程序在语法上是否正确（即，case语句中的parse_error子句均未执行，并且match始终看到它期望看到的内容）。为了对编译器的其余部分有用（必须用其他语言生成等效的目标程序），解析器必须将解析树或程序片段的其他表示保存为显式数据结构。要保存解析树本身，我们可以在执行表示这些子节点的递归子例程和匹配调用之前立即分配并链接记录以表示节点的子节点。我们需要向每个递归例程传递一个参数，该参数指向要扩展的记录（即要发现其子节点）。过程匹配还需要在树的叶子中保存有关某些标记（例如，标识符和文字的字符串表示）的信息。

Without additional code (not shown in Figure 2.17), the parser merely verifies that the program is syntactically correct (i.e., that none of the otherwise parse_error clauses in the case statements are executed and that match always sees what it expects to see). To be of use to the rest of the compiler—which must produce an equivalent target program in some other language—the parser must save the parse tree or some other representation of program fragments as an explicit data structure. To save the parse tree itself, we can allocate and link together records to represent the children of a node immediately before executing the recursive subroutines and match invocations that represent those children. We shall need to pass each recursive routine an argument that points to the record that is to be expanded (i.e., whose children are to be discovered). Procedure match will also need to save information about certain tokens (e.g., character-string representations of identifiers and literals) in the leaves of the tree.

正如我们在第 1 章中看到的，解析树包含大量无关细节，这些细节无需为编译器的其余部分保存。因此，解析器很少显式地构造完整的解析树。它更经常生成抽象语法树或其他更简洁的表示。在递归下降编译器中，可以通过仅在递归调用的子集中分配和链接记录来创建语法树。

As we saw in Chapter 1, the parse tree contains a great deal of irrelevant detail that need not be saved for the rest of the compiler. It is therefore rare for a parser to construct a full parse tree explicitly. More often it produces an abstract syntax tree or some other more terse representation. In a recursive descent compiler, a syntax tree can be created by allocating and linking together records in only a subset of the recursive calls.

编写递归下降解析器最棘手的部分是找出应该用哪些标记来标记case语句的分支。每个分支代表一个产生式：即子程序所对应符号的一种可能的展开。标记X 可以预测产生式，原因有二：(1)产生式的右侧在递归展开时，可能产生一个以X开头的字符串，或 (2) 右侧可能不产生任何结果（即，它是ε ，或者是可以递归产生ε的非终结符字符串），并且X可能开始产生接下来的结果。我们将在第 2.3.3 节中使用称为 FIRST 和 FOLLOW 的集合来形式化这个预测概念，并展示如何从 LL(1) CFG 自动推导它们。

The trickiest part of writing a recursive descent parser is figuring out which tokens should label the arms of the case statements. Each arm represents one production: one possible expansion of the symbol for which the subroutine was named. The tokens that label a given arm are those that predict the production. A token X may predict a production for either of two reasons: (1) the right-hand side of the production, when recursively expanded, may yield a string beginning with X, or (2) the right-hand side may yield nothing (i.e., it is ε, or a string of nonterminals that may recursively yield ε), and X may begin the yield of what comes next. We will formalize this notion of prediction in Section 2.3.3, using sets called FIRST and FOLLOW, and show how to derive them automatically from an LL(1) CFG.

检查你的理解

Check Your Understanding

20. 解析的固有“大 O”复杂度是多少？实际编译器中使用的解析器的复杂度是多少？

20. What is the inherent “big-O” complexity of parsing? What is the complexity of parsers used in real compilers?

21. 总结一下 LL 和 LR 解析的区别。哪一个又被称为“自下而上”？“自上而下”？哪一个又被称为“预测”？“移位归约”？“LL”和“LR”分别代表什么？

21. Summarize the difference between LL and LR parsing. Which one of them is also called “bottom-up”? “Top-down”? Which one is also called “predictive”? “Shift-reduce”? What do “LL” and “LR” stand for?

22. 在生产编译器中哪种解析器（自上而下还是自下而上）最常见？

22. What kind of parser (top-down or bottom-up) is most common in production compilers?

23. 为什么最右边的推导有时被称为规范的？

23. Why are right-most derivations sometimes called canonical?

24.LR  (1)中的“1”有什么意义？

24. What is the significance of the “1” in LR(1)?

25. 为什么我们希望（或需要）针对不同的解析算法使用不同的语法？

25. Why might we want (or need) different grammars for different parsing algorithms?

26. 什么是epsilon 产生式？

26. What is an epsilon production?

27. 什么是递归下降解析器？为什么它们主要用于小型语言？

27. What are recursive descent parsers? Why are they used mostly for small languages?

28. 解析器如何构造显式的解析树或语法树？

28. How might a parser construct an explicit parse tree or syntax tree?

2.3.3 表驱动的自上而下的解析

2.3.3 Table-Driven Top-Down Parsing

例 2.33

Example 2.33

自上而下解析的驱动程序和表

Driver and table for top-down parsing

在递归下降解析器中，case语句的每个分支都对应一个产生式，并包含与该产生式右侧的符号相对应的解析例程和匹配调用。在解析过程中的任何给定点，如果我们考虑当前调用堆栈中解析例程调用中程序计数器以外的调用（尚未发生的调用），我们将获得解析器期望从此处到程序结束之间看到的符号列表。表驱动的自上而下的解析器维护一个包含相同符号列表的显式堆栈。

In a recursive descent parser, each arm of a case statement corresponds to a production, and contains parsing routine and match calls corresponding to the symbols on the right-hand side of that production. At any given point in the parse, if we consider the calls beyond the program counter (the ones that have yet to occur) in the parsing routine invocations currently in the call stack, we obtain a list of the symbols that the parser expects to see between here and the end of the program. A table-driven top-down parser maintains an explicit stack containing this same list of symbols.

图 2.19给出了这种解析器的伪代码。该代码与语言无关。它需要一个与语言相关的解析表，该解析表通常由自动工具生成。对于图 2.16中的计算器语法，该表如图2.20所示。■

Pseudocode for such a parser appears in Figure 2.19. The code is language independent. It requires a language-dependent parsing table, generally produced by an automatic tool. For the calculator grammar of Figure 2.16, the table appears in Figure 2.20. ■

例 2.34

Example 2.34

“求和与平均”程序的表驱动解析

Table-driven parse of the “sum and average” program

为了说明该算法，图 2.21显示了示例 2.24中的求和平均程序的堆栈和输入随时间的变化情况。解析器循环迭代，从堆栈中弹出顶部符号并执行以下操作：如果弹出的符号是终结符，解析器将尝试将其与来自扫描器的传入标记进行匹配。如果匹配失败，解析器将宣布语法错误并启动某种错误恢复（参见第 2.3.5 节）。如果弹出的符号是非终结符，解析器将使用该非终结符和下一个可用的输入标记来索引二维表，该表告诉它要预测哪个产生式（或者是否宣布语法错误并启动恢复）。

To illustrate the algorithm, Figure 2.21 shows a trace of the stack and the input over time, for the sum-and-average program of Example 2.24. The parser iterates around a loop in which it pops the top symbol off the stack and performs the following actions: If the popped symbol is a terminal, the parser attempts to match it against an incoming token from the scanner. If the match fails, the parser announces a syntax error and initiates some sort of error recovery (see Section 2.3.5). If the popped symbol is a nonterminal, the parser uses that nonterminal together with the next available input token to index into a two-dimensional table that tells it which production to predict (or whether to announce a syntax error and initiate recovery).

最初，解析堆栈包含语法的起始符号（在我们的例子中是程序）。当它预测一个产生式时，解析器会以相反的顺序将右侧符号推送到解析堆栈上，因此这些符号中的第一个符号最终位于堆栈顶部。当我们匹配结束标记标记$$时，解析成功完成。假设$$只在语法中出现一次，在第一个产生式的末尾，并且扫描器只在文件末尾返回此标记，则任何语法错误都一定会表现为失败的匹配或表中的错误条目。■

Initially, the parse stack contains the start symbol of the grammar (in our case, program). When it predicts a production, the parser pushes the right-hand-side symbols onto the parse stack in reverse order, so the first of those symbols ends up at top-of-stack. The parse completes successfully when we match the end marker token, $$. Assuming that $$ appears only once in the grammar, at the end of the first production, and that the scanner returns this token only at end-of-file, any syntax error is guaranteed to manifest itself either as a failed match or as an error entry in the table. ■

正如我们在第 2.3.1 节末尾所暗示的，预测集是用称为 FIRST 和 FOLLOW 的更简单的集合来定义的，其中 FIRST( A ) 是所有可以作为A开头的标记的集合，而 FOLLOW( A ) 是某个有效程序中可以跟在A之后的所有标记的集合。如果我们以显而易见的方式扩展 FIRST 的定义域以包括符号字符串，那么我们说产生式A → β的预测集是 FIRST ( β )，加上如果β ⇒ ^* ε 的FOLLOW( A ) 。为了符号方便，我们定义谓词 EPS 使得 EPS( β ) ≡ β ⇒ ^* ε。

As we hinted at the end of Section 2.3.1, predict sets are defined in terms of simpler sets called FIRST and FOLLOW, where FIRST(A) is the set of all tokens that could be the start of an A and FOLLOW(A) is the set of all tokens that could come after an A in some valid program. If we extend the domain of FIRST in the obvious way to include strings of symbols, we then say that the predict set of a production A → β is FIRST (β), plus FOLLOW(A) if β ⇒^* ε. For notational convenience, we define the predicate EPS such that EPS(β) ≡ β ⇒^* ε.

例 2.35

Example 2.35

计算器语言的预测集

Predict sets for the calculator language

我们可以用计算器语法（图 2.16 ）来说明构造这些集合的算法。我们从语法的“明显”事实开始，然后以此为基础进行归纳构建。如果我们用普通的 BNF（没有 EBNF '|' 构造）重写该语法，那么它有 19 个产生式。这些“明显”的事实来自右侧相邻的符号对。在第一个产生式中，我们可以看到$$ ∈ FOLLOW( stmt_list )。在第三个产生式（stmt_list → ε）中，EPS( stmt_list ) = true。在第四个产生式（stmt → id := expr）中，id ∈ FIRST( stmt )（同样 := ∈ FOLLOW( id )，但事实证明非终结符不需要 FOLLOW 集）。在第五个和第六个产生式（stmt → read id | write expr）中，{ read , write } ⊂ FIRST( stmt )。“显而易见”的事实的完整集合如图2.22所示。

We can illustrate the algorithm to construct these sets using our calculator grammar (Figure 2.16). We begin with “obvious” facts about the grammar and build on them inductively. If we recast the grammar in plain BNF (no EBNF '|' constructs), then it has 19 productions. The “obvious” facts arise from adjacent pairs of symbols in right-hand sides. In the first production, we can see that $$ ∈ FOLLOW(stmt_list). In the third (stmt_list → ε), EPS(stmt_list) = true. In the fourth production (stmt → id := expr), id ∈ FIRST(stmt) (also := ∈ FOLLOW(id), but it turns out we don't need FOLLOW sets for nonterminals). In the ifth and sixth productions (stmt → read id | write expr), {read, write} ⊂ FIRST(stmt). The complete set of “obvious” facts appears in Figure 2.22.

从“显而易见”的事实中，我们可以在第二次遍历语法时推断出更大的事实集合。例如，在第二个产生式（stmt_list → stmt stmt_list）中，我们可以推断出 { id , read , write } ⊂ FIRST( stmt_list )，因为我们已经知道 { id , read , write } ⊂ FIRST( stmt )，并且stmt_list可以从stmt开始。类似地，在第一个产生式中，我们可以推断出$$ ∈ FIRST( program )，因为我们已经知道 EPS( stmt_list ) = true。

From the “obvious” facts we can deduce a larger set of facts during a second pass over the grammar. For example, in the second production (stmt_list → stmt stmt_list) we can deduce that {id, read, write} ⊂ FIRST(stmt_list), because we already know that {id, read, write} ⊂ FIRST(stmt), and a stmt_list can begin with a stmt. Similarly, in the first production, we can deduce that $$ ∈ FIRST(program), because we already know that EPS(stmt_list) = true.

设计与实现

Design & Implementation

2.7 递归下降和表驱动 LL 解析

2.7 Recursive descent and table-driven LL parsing

当试图理解递归下降和表驱动 LL 解析之间的联系时，很容易想象表驱动解析器的显式堆栈反映了递归下降解析器的隐式调用堆栈，但事实并非如此。

When trying to understand the connection between recursive descent and table-driven LL parsing, it is tempting to imagine that the explicit stack of the table-driven parser mirrors the implicit call stack of the recursive descent parser, but this is not the case.

可视化两种自上而下解析实现的更好方法是记住它们都是通过深度优先从左到右的遍历来发现解析树。当我们处于解析中的给定点（例如此处显示的树中带圆圈的节点）时，递归下降解析器的隐式调用堆栈会为返回根路径上的每个节点保留一个框架，该框架是在调用与该节点对应的例程时创建的。（此路径显示为灰色。）

A better way to visualize the two implementations of top-down parsing is to remember that both are discovering a parse tree via depth-first left-to-right traversal. When we are at a given point in the parse—say the circled node in the tree shown here—the implicit call stack of a recursive descent parser holds a frame for each of the nodes on the path back to the root, created when the routine corresponding to that node was called. (This path is shown in grey.)

但这些节点并不重要。对于其余的解析来说，重要的是（如这里的白色路径所示）对递归下降例程的 case 语句臂的即将到来的调用。这些调用（这些解析树节点）正是表驱动 LL 解析器的显式堆栈的内容。

But these nodes are immaterial. What matters for the rest of the parse—as shown on the white path here—are the upcoming calls on the case statement arms of the recursive descent routines. Those calls—those parse tree nodes—are precisely the contents of the explicit stack of a table-driven LL parser.

在第十一个产生式（factor_tail → mult_op factor factor_tail）中，我们可以推出 {(, id , number } ⊂ FOLLOW( mult_op )，因为我们已经知道 {(, id , number } ⊂ FIRST( factor )，并且factor在右侧跟在mult_op后面。在产生式expr → term term_tail中，我们可以推出) ∈ FOLLOW( term_tail )，因为我们已经知道) ∈ FOLLOW( expr )，并且term_tail可以是expr的最后一部分。在同一个产生式中，我们还可以推出) ∈ FOLLOW( term )，因为term_tail可以生成ε (EPS( term_tail ) = true )，从而允许term成为expr的最后一部分。

In the eleventh production (factor_tail → mult_op factor factor_tail), we can deduce that {(, id, number} ⊂ FOLLOW(mult_op), because we already know that {(, id, number} ⊂ FIRST(factor), and factor follows mult_op in the right-hand side. In the production expr → term term_tail, we can deduce that) ∈ FOLLOW(term_tail), because we already know that ) ∈ FOLLOW(expr), and a term_tail can be the last part of an expr. In this same production, we can also deduce that) ∈ FOLLOW(term), because the term_tail can generate ε (EPS(term_tail) = true), allowing a term to be the last part of an expr.

我们可以从第二遍语法中学到更多东西，但上面的例子涵盖了所有不同类型的情况。为了完成我们的计算，我们继续对语法进行额外的遍历，直到我们不再学到任何东西（即，我们不向任何 FIRST 和 FOLLOW 集添加任何内容）。然后我们构造 PREDICT 集。所有三个集合的最终版本如图2.23所示。图 2.20的解析表直接来自 PREDICT。■

There is more that we can learn from our second pass through the grammar, but the examples above cover all the different kinds of cases. To complete our calculation, we continue with additional passes over the grammar until we don't learn any more (i.e., we don't add anything to any of the FIRST and FOLLOW sets). We then construct the PREDICT sets. Final versions of all three sets appear in Figure 2.23. The parse table of Figure 2.20 follows directly from PREDICT. ■

图 2.24中更正式地给出了计算 EPS、FIRST、FOLLOW 和 PREDICT 集的算法。它依赖于以下定义：

The algorithm to compute EPS, FIRST, FOLLOW, and PREDICT sets appears, a bit more formally, in Figure 2.24. It relies on the following definitions:

EPS( α ) == 如果α ⇒ ^* ε则为真，否则为假

EPS(α) ≡ if α ⇒^* ε then true else false

FIRST( α ) ≡ { c : α⇒ ^* cβ }

FIRST(α) ≡ {c : α ⇒^* c β }

FOLLOW( A ) ≡ {c : S ⇒ ⁺ α A c β }

FOLLOW(A) ≡ {c : S ⇒⁺ α A c β }

PREDICT( A → α ) ≡ FIRST( α ) ∪ （如果 EPS( α ) 则 FOLLOW( A ) 否则 ∅）

PREDICT(A → α) ≡ FIRST(α) ∪ ( if EPS(α) then FOLLOW(A) else ∅)

PREDICT 的定义假设该语言已经增加了结束标记，即 FOLLOW( S ) = {$$}。请注意，长度大于 1 的字符串的 FIRST 集和 EPS 值是根据需要计算的；它们是不显式存储。算法保证终止（即收敛到一个解决方案），因为 FIRST 和 FOLLOW 集的大小受语法中终端数量的限制。

The definition of PREDICT assumes that the language has been augmented with an end marker—that is, that FOLLOW(S) = {$$}. Note that FIRST sets and EPS values for strings of length greater than one are calculated on demand; they are not stored explicitly. The algorithm is guaranteed to terminate (i.e., converge on a solution), because the sizes of the FIRST and FOLLOW sets are bounded by the number of terminals in the grammar.

如果在计算 PREDICT 集的过程中，我们发现某个标记属于多个具有相同左侧的产生式的 PREDICT 集，则该语法不是 LL(1)，因为当左侧位于解析堆栈的顶部（或者我们在递归下降解析器中左侧的子例程中）并且我们看到该标记出现在输入中时，我们将无法选择使用哪个产生式。这种歧义称为预测-预测冲突；它可能是因为同一个标记可以开始多个右侧，或者因为它可以开始一个右侧并且也可以出现在某个有效程序的左侧之后，并且一个可能的右侧可以生成ε而产生的。

If in the process of calculating PREDICT sets we find that some token belongs to the PREDICT set of more than one production with the same left-hand side, then the grammar is not LL(1), because we will not be able to choose which of the productions to employ when the left-hand side is at the top of the parse stack (or we are in the left-hand side's subroutine in a recursive descent parser) and we see the token coming up in the input. This sort of ambiguity is known as a predict-predict conflict; it can arise either because the same token can begin more than one right-hand side, or because it can begin one right-hand side and can also appear after the left-hand side in some valid program, and one possible right-hand side can generate ε.

检查你的理解

Check Your Understanding

29. 描述上下文无关文法中两个无法自上而下解析的常见习语。

29. Describe two common idioms in context-free grammars that cannot be parsed top-down.

30. 什么是“悬垂else ”问题？现代语言中如何避免这个问题？

30. What is the “dangling else“ problem? How is it avoided in modern languages?

31. 讨论递归下降和表驱动自上而下解析之间的异同。

31. Discuss the similarities and differences between recursive descent and table-driven top-down parsing.

32.  FIRST 和 FOLLOW 集是什么？它们有什么用途？

32. What are FIRST and FOLLOW sets? What are they used for?

33. 在什么情况下，自上而下的解析器会预测产生式A → α？

33. Under what circumstances does a top-down parser predict the production A → α?

34. 哪些“明显的”事实构成了 FIRST 集和 FOLLOW 集构建的基础？

34. What sorts of “obvious” facts form the basis of FIRST set and FOLLOW set construction?

35. 概述用于完成 FIRST 和 FOLLOW 集构建的算法。我们如何知道何时完成？

35. Outline the algorithm used to complete the construction of FIRST and FOLLOW sets. How do we know when we are done?

36. 我们如何知道一个语法不是LL(1)的？

36. How do we know when a grammar is not LL(1)?

2.3.4 自底向上解析

2.3.4 Bottom-Up Parsing

从概念上讲，正如我们在2.3 节开头看到的那样，自下而上的解析器通过维护解析树的部分完成的子树森林来工作，每当它识别出输入字符串最右侧派生中使用的某些产生式右侧的符号时，它就会将这些子树连接在一起。它会创建一个新的内部节点，并将连接在一起的树的根节点作为该节点的子节点。

Conceptually, as we saw at the beginning of Section 2.3, a bottom-up parser works by maintaining a forest of partially completed subtrees of the parse tree, which it joins together whenever it recognizes the symbols on the right-hand side of some production used in the right-most derivation of the input string. It creates a new internal node and makes the roots of the joined-together trees the children of that node.

实际上，自下而上的解析器几乎总是表驱动的。它将部分完成的子树的根保存在堆栈中。当它从扫描器将标记移入堆栈。当它识别出堆栈顶部的几个符号构成右侧时，它会通过弹出堆栈并将左侧推入其位置来将这些符号缩减到其左侧。堆栈的作用是自上而下和自下而上解析之间的第一个重要区别：自上而下的解析器的堆栈包含解析器期望在未来看到的内容的列表；自下而上的解析器的堆栈包含解析器过去已经看到的内容的记录。

In practice, a bottom-up parser is almost always table-driven. It keeps the roots of its partially completed subtrees on a stack. When it accepts a new token from the scanner, it shifts the token into the stack. When it recognizes that the top few symbols on the stack constitute a right-hand side, it reduces those symbols to their left-hand side by popping them off the stack and pushing the left-hand side in their place. The role of the stack is the first important difference between top-down and bottom-up parsing: a top-down parser's stack contains a list of what the parser expects to see in the future; a bottom-up parser's stack contains a record of what the parser has already seen in the past.

规范推导

Canonical Derivations

例 2.36

Example 2.36

导出id 列表

Derivation of an id list

我们之前还提到，自下而上的解析器的操作会反向追踪最右侧（规范）推导。从左到右的部分子树的根与剩余的输入一起构成最右侧推导的句子形式。例如，在图 2.14的右侧，我们有以下一系列步骤：

We also noted earlier that the actions of a bottom-up parser trace out a right-most (canonical) derivation in reverse. The roots of the partial subtrees, left-to-right, together with the remaining input, constitute a sentential form of the right-most derivation. On the right-hand side of Figure 2.14, for example, we have the following series of steps:

堆栈内容（部分树的根）	剩余输入
ε	A、B、C；
id（A）	，B，C；
id（A），	B、C；
id（A），id（B）	，C；
id（A），id（B），	碳；
id（A）、id（B）、id（C）	；
id(A),id(B),id(C) ；
id（A），id（B），id（C）id_list_tail
id（A），id（B）id_list_tail
id (A) id_list_tail
id_列表

最后四行（不仅仅是将标记移入森林的行）对应于最右边的推导：

The last four lines (the ones that don't just shift tokens into the forest) correspond to the right-most derivation:

id_list⇒id id_list_tail​

id_list ⇒ id id_list_tail

 ⇒ id，id id_list_tail

 ⇒ id, id id_list_tail

 ⇒ id，id，id id_list_tail

 ⇒ id, id, id id_list_tail

 ⇒ id，id，id；

 ⇒ id, id, id ;

在解析的每一步中需要连接在一起以表示向后推导的下一步的符号称为句柄。在上面的解析轨迹中，句柄被加了下划线。■

The symbols that need to be joined together at each step of the parse to represent the next step of the backward derivation are called the handle of the sentential form. In the parse trace above, the handles are underlined. ■

例 2.37

Example 2.37

计算器语言的自下而上的语法

Bottom-up grammar for the calculator language

在我们的id_list示例中，直到将整个输入移到堆栈上时才找到句柄。一般来说情况并非如此。我们可以通过检查计算器语言的 LR 版本来获得更现实的示例，如图2.25所示。虽然图 2.16的 LL 语法可以自下而上地进行解析，但是图 2.25中的版本更可取，原因有二。首先，它对stmt_list使用左递归产生式。左递归允许解析器在进行过程中折叠长语句列表，而不是等到整个列表在堆栈上然后从末尾折叠它。其次，它对expr和term使用左递归产生式。这些产生式捕获左结合性，同时仍将运算符及其操作数保持在同一右侧，这是我们在自上而下的语法中无法做到的。■

In our id_list example, no handles were found until the entire input had been shifted onto the stack. In general this will not be the case. We can obtain a more realistic example by examining an LR version of our calculator language, shown in Figure 2.25. While the LL grammar of Figure 2.16 can be parsed bottom-up, the version in Figure 2.25 is preferable for two reasons. First, it uses a left-recursive production for stmt_list. Left recursion allows the parser to collapse long statement lists as it goes along, rather than waiting until the entire list is on the stack and then collapsing it from the end. Second, it uses left-recursive productions for expr and term. These productions capture left associativity while still keeping an operator and its operands together in the same right-hand side, something we were unable to do in a top-down grammar. ■

使用 LR 项目建模解析

Modeling a Parse with LR Items

例 2.38

Example 2.38

自下而上解析“求和与平均”程序

Bottom-up parse of the “sum and average” program

假设我们要解析示例 2.24中的求和与平均值程序：

Suppose we are to parse the sum-and-average program from Example 2.24:

读A

read A

读B

read B

总和 := A + B

sum := A + B

写总和

write sum

写出总和 / 2

write sum / 2

成功的关键在于弄清楚我们何时到达右侧的末尾 — 即，何时我们在解析堆栈的顶部有一个句柄。诀窍是跟踪我们可能在任何特定时间“处于”的产生式集合，以及我们可能处于这些产生式的哪个位置的指示。

The key to success will be to figure out when we have reached the end of a right-hand side—that is, when we have a handle at the top of the parse stack. The trick is to keep track of the set of productions we might be “in the middle of” at any particular time, together with an indication of where in those productions we might be.

当我们开始执行时，解析堆栈是空的，我们正处于程序的产生式的开头。（一般来说，我们可以假设只有一个产生式，其起始符号在左侧；很容易修改任何语法都可以做到这一点。）我们可以在产生式的右侧用 • 来表示我们的位置——更具体地说，是解析堆栈顶部所表示的位置：

When we begin execution, the parse stack is empty and we are at the beginning of the production for program. (In general, we can assume that there is only one production with the start symbol on the left-hand side; it is easy to modify any grammar to make this the case.) We can represent our location—more specifically, the location represented by the top of the parse stack—with a • in the right-hand side of the production:

程序 → • stmt_list $$

program → • stmt_list $$

当一个产生式被添加一个 • 时，它就被称为 LR项。由于该项中的 • 紧挨着一个非终结符（即stmt_list ）前面，我们可能即将看到该非终结符在输入中出现。这种可能性意味着我们可能处于某个产生式的开头，其左侧是stmt_list ：

When augmented with a •, a production is called an LR item. Since the • in this item is immediately in front of a nonterminal—namely stmt_list—we may be about to see the yield of that nonterminal coming up on the input. This possibility implies that we may be at the beginning of some production with stmt_list on the left-hand side:

程序→ • stmt_list $$

program → • stmt_list $$

stmt_list → • stmt_list stmt

stmt_list → • stmt_list stmt

stmt_list → • stmt

stmt_list → • stmt

并且，由于stmt是非终结符，我们也可能位于任何左侧是stmt的产生式的开头：

And, since stmt is a nonterminal, we may also be at the beginning of any production whose left-hand side is stmt:

（状态 0）

(State 0)

程序→ • stmt_list $$

program → • stmt_list $$

stmt_list → • stmt_list stmt

stmt_list → • stmt_list stmt

stmt_list → • stmt

stmt_list → • stmt

stmt → • id := expr

stmt → • id := expr

stmt → • 读取 id

stmt → • read id

stmt → • 写入expr

stmt → • write expr

由于所有这些最后的产生式都以终结符开头，因此不需要在列表中添加任何附加项。原始项（program → • stmt_list $$）称为列表的基础。附加项是它的闭包。列表表示解析器的初始状态。当我们移位和归约时，项集将发生变化，始终指示哪些产生式可能是接下来在输入字符串的推导中使用的正确产生式。如果我们到达某个项在右侧末尾有 • 的状态，我们可以通过该产生式来归约。否则，像当前情况一样，我们必须移位。请注意，如果我们需要移位，但传入的标记不能跟在当前状态的任何项中的 • 之后，则发生了语法错误。我们将在C-2.3.5 节中更详细地考虑错误恢复。

Since all of these last productions begin with a terminal, no additional items need to be added to our list. The original item (program → • stmt_list $$) is called the basis of the list. The additional items are its closure. The list represents the initial state of the parser. As we shift and reduce, the set of items will change, always indicating which productions may be the right one to use next in the derivation of the input string. If we reach a state in which some item has the • at the end of the right-hand side, we can reduce by that production. Otherwise, as in the current situation, we must shift. Note that if we need to shift, but the incoming token cannot follow the • in any item of the current state, then a syntax error has occurred. We will consider error recovery in more detail in Section C-2.3.5.

我们即将收到的 token 是read。一旦将其移入堆栈，我们就知道我们处于以下状态：

Our upcoming token is a read. Once we shift it onto the stack, we know we are in the following state:

（状态 1）

(State 1)

stmt → 读取 • id

stmt → read • id

此状态具有单个基础项和一个空闭包——• 位于终端之前。在移动 A 之后，我们有

This state has a single basis item and an empty closure—the • precedes a terminal. After shifting the A, we have

（状态 1'）

(State 1')

stmt → 读取 ID •

stmt → read id •

我们现在知道read id是句柄，我们必须进行归约。归约会从解析堆栈中弹出两个符号，并在其位置推送一个stmt，但新状态应该是什么？如果我们想象回到我们移动read（右侧的第一个符号）的时间点，我们可以看到答案。当时我们处于上面标记为“状态 0”的状态，输入中即将到来的标记（尽管我们当时没有查看它们）是read id。我们现在已经使用了这些标记，并且我们知道它们构成了一个stmt。通过将stmt推送到堆栈上，我们本质上已经用stmt替换了输入流上的read id，然后将非终结符（而不是其产量）“移入”堆栈。由于状态 0 中的一项是

We now know that read id is the handle, and we must reduce. The reduction pops two symbols off the parse stack and pushes a stmt in their place, but what should the new state be? We can see the answer if we imagine moving back in time to the point at which we shifted the read—the first symbol ofthe right-hand side. At that time we were in the state labeled “State 0” above, and the upcoming tokens on the input (though we didn't look at them at the time) were read id. We have now consumed these tokens, and we know that they constituted a stmt. By pushing a stmt onto the stack, we have in essence replaced read id with stmt on the input stream, and have then “shifted” the nonterminal, rather than its yield, into the stack. Since one of the items in State 0 was

stmt_list → • stmt

stmt_list → • stmt

我们现在有

we now have

（状态 0'）

(State 0')

stmt_list → stmt •

stmt_list → stmt •

我们必须再次进行归约。我们从堆栈中删除stmt ，并在其位置推送一个stmt_list 。我们可以再次将此视为在状态 0 中“移动” stmt_list。由于状态 0 中的两个项目在 • 之后有一个stmt_list，因此我们不知道（不向前看）哪个产生式将是下一个用于推导的产生式，但我们不必知道。自下而上解析相对于自上而下解析的主要优势在于，我们不需要提前预测我们将扩展哪个产生式。

Again we must reduce. We remove the stmt from the stack and push a stmt_list in its place. Again we can see this as “shifting” a stmt_list when in State 0. Since two of the items in State 0 have a stmt_list after the •, we don't know (without looking ahead) which of the productions will be the next to be used in the derivation, but we don't have to know. The key advantage of bottom-up parsing over top-down parsing is that we don't need to predict ahead of time which production we shall be expanding.

我们的新状态如下：

Our new state is as follows:

（状态 2）

(State 2)

程序→ stmt_list • $$

program → stmt_list • $$

stmt_list → stmt_list • stmt

stmt_list → stmt_list • stmt

stmt → • id := expr

stmt → • id := expr

stmt → • 读取 id

stmt → • read id

stmt → • 写入expr

stmt → • write expr

前两个产生式是基础；其他产生式是闭包。由于没有项目以 • 结尾，我们移动下一个标记，该标记又恰好是 read ，将我们带回到状态 1。移动B再次将我们带回到状态 1'，此时我们进行归约。不过，这一次，我们在移动左侧stmt之前返回状态 2 而不是状态 0。为什么？因为当我们开始读取右侧时，我们处于状态 2。■

The first two productions are the basis; the others are the closure. Since no item has a • at the end, we shift the next token, which happens again to be a read, taking us back to State 1. Shifting the B takes us to State 1' again, at which point we reduce. This time however, we go back to State 2 rather than State 0 before shifting the left-hand-side stmt. Why? Because we were in State 2 when we began to read the right-hand side. ■

特征有限状态机和 LR 解析变体

The Characteristic Finite-State Machine and LR Parsing Variants

LR 系列解析器通过将已遍历的状态与语法符号一起推送到解析堆栈中来跟踪它们。事实上，驱动解析算法的是状态（而不是符号）：它们告诉我们在右侧开始时我们处于什么状态。具体来说，当状态和输入的组合告诉我们需要使用产生式A → α进行归约时，我们会从堆栈中弹出长度（α）个符号，以及我们移动的状态记录在移动这些符号时，这些弹出窗口会显示我们在移动之前的状态，这样我们就可以返回到该状态并继续操作，就像我们一开始就看到了A一样。

An LR-family parser keeps track of the states it has traversed by pushing them into the parse stack, along with the grammar symbols. It is in fact the states (rather than the symbols) that drive the parsing algorithm: they tell us what state we were in at the beginning of a right-hand side. Specifically, when the combination of state and input tells us we need to reduce using production A → α, we pop length(α) symbols off the stack, together with the record of states we moved through while shifting those symbols. These pops expose the state we were in immediately prior to the shifts, allowing us to return to that state and proceed as if we had seen A in the first place.

我们可以将 LR 系列解析器的移位规则视为有限自动机的转换函数，与我们用来建模扫描仪的自动机非常相似。自动机的每个状态都对应于一个项目列表，这些项目指示解析器在解析过程中的某个特定点可能处于的位置。输入符号X（可能是终结符或非终结符）的转换移动到一个状态，该状态的基础由右侧的X上的 • 已移动的项目以及需要添加为闭包的任何项目组成。这些列表由自下而上的解析器生成器构建，以构建自动机，但在解析过程中不需要。

We can think of the shift rules of an LR-family parser as the transition function of a finite automaton, much like the automata we used to model scanners. Each state of the automaton corresponds to a list of items that indicate where the parser might be at some specific point in the parse. The transition for input symbol X (which may be either a terminal or a nonterminal) moves to a state whose basis consists of items in which the • has been moved across an X in the right-hand side, plus whatever items need to be added as closure. The lists are constructed by a bottom-up parser generator in order to build the automaton, but are not needed during parsing.

事实证明，LR 系列解析器中较简单的成员 LR(0)、SLR(1) 和 LALR(1) 都使用相同的自动机，称为特征有限状态机(CFSM)。完整的 LR 解析器使用具有（对于大多数语法）更多状态的机器。这些算法之间的差异在于它们如何处理包含移位-归约冲突的状态- 一个项的 • 位于终结符前面（表明需要移位），另一个项的 • 位于右侧末尾（表明需要归约）。LR(0) 解析器仅在没有这样的状态时工作。可以证明，通过添加结束标记（即$$），任何可以自下而上确定性解析的语言都具有 LR(0) 语法。不幸的是，实际编程语言的 LR(0) 语法往往非常大且不直观。

It turns out that the simpler members of the LR family of parsers—LR(0), SLR(1), and LALR(1)—all use the same automaton, called the characteristic finite-state machine, or CFSM. Full LR parsers use a machine with (for most grammars) a much larger number of states. The differences between the algorithms lie in how they deal with states that contain a shift-reduce conflict—one item with the • in front of a terminal (suggesting the need for a shift) and another with the • at the end of the right-hand side (suggesting the need for a reduction). An LR(0) parser works only when there are no such states. It can be proven that with the addition of an end-marker (i.e., $$), any language that can be deterministically parsed bottom-up has an LR(0) grammar. Unfortunately, the LR(0) grammars for real programming languages tend to be prohibitively large and unintuitive.

SLR（简单 LR）解析器会查看即将到来的输入并使用 FOLLOW 集来解决冲突。仅当即将到来的标记在 FOLLOW( α ) 中时，SLR 解析器才会通过A → α调用约简。但是，如果标记也位于状态其他项中 • 后面的任何符号的 FIRST 集中，则它仍然会看到冲突。事实证明，在重要的情况下，标记可能在有效程序的某个地方跟随给定的非终结符，但永远不会在当前状态描述的上下文中出现。对于这些情况，全局 FOLLOW 集过于粗糙。LALR（前瞻 LR）解析器通过使用局部（特定于状态的）前瞻来改进 SLR。

SLR (simple LR) parsers peek at upcoming input and use FOLLOW sets to resolve conflicts. An SLR parser will call for a reduction via A → α only if the upcoming token(s) are in FOLLOW(α). It will still see a conflict, however, if the tokens are also in the FIRST set of any of the symbols that follow a • in other items of the state. As it turns out, there are important cases in which a token may follow a given nonterminal somewhere in a valid program, but never in a context described by the current state. For these cases global FOLLOW sets are too crude. LALR (look-ahead LR) parsers improve on SLR by using local (state-specific) look-ahead instead.

当同一组项目可能出现在 CFSM 中的两条不同路径上时，LALR 解析器中仍会出现冲突。两条路径最终都会处于同一状态，此时特定于状态的前瞻无法再区分它们。完整的 LR 解析器会复制状态，以便在它们的本地前瞻不同时保持路径不相交。

Conflicts can still arise in an LALR parser when the same set of items can occur on two different paths through the CFSM. Both paths will end up in the same state, at which point state-specific look-ahead can no longer distinguish between them. A full LR parser duplicates states in order to keep paths disjoint when their local look-aheads are different.

LALR 解析器是实践中最常见的自下而上的解析器。它们的大小和速度与 SLR 解析器相同，但能够解决更多冲突。实际编程语言的完整 LR 解析器往往非常大。一些研究人员已经开发出减少完整 LR 表大小的技术，但 LALR 在实践中运行良好，通常不需要完整 LR 的额外复杂性。Yacc /bison为 LALR 解析器生成 C 代码。

LALR parsers are the most common bottom-up parsers in practice. They are the same size and speed as SLR parsers, but are able to resolve more conflicts. Full LR parsers for real programming languages tend to be very large. Several researchers have developed techniques to reduce the size of full-LR tables, but LALR works sufficiently well in practice that the extra complexity of full LR is usually not required. Yacc/bison produces C code for an LALR parser.

自下而上解析表

Bottom-Up Parsing Tables

与表驱动的 LL(1) 解析器一样，SLR(1)、LALR(1) 或 LR(1) 解析器执行循环，在该循环中反复检查二维表以找出要采取的操作。但是，LR 系列解析器不使用当前输入标记和堆栈顶部的非终结符来索引表，而是使用当前输入标记和当前解析器状态（可在堆栈顶部找到）。“Shift”表条目表示应推送的状态。“Reduce”表条目表示应弹出的状态数和应推回到输入流中的非终结符，以便按弹出未覆盖的状态进行移动。对于减少产生式右侧的每个符号，始终有一个弹出状态。可以使用未覆盖的状态和新识别的非终结符索引表来找到下一个要推送的状态。

Like a table-driven LL(1) parser, an SLR(1), LALR(1), or LR(1) parser executes a loop in which it repeatedly inspects a two-dimensional table to find out what action to take. However, instead of using the current input token and top-of-stack nonterminal to index into the table, an LR-family parser uses the current input token and the current parser state (which can be found at the top of the stack). “Shift” table entries indicate the state that should be pushed. “Reduce” table entries indicate the number of states that should be popped and the nonterminal that should be pushed back onto the input stream, to be shifted by the state uncovered by the pops. There is always one popped state for every symbol on the right-hand side of the reducing production. The state to be pushed next can be found by indexing into the table using the uncovered state and the newly recognized nonterminal.

例 2.39

Example 2.39

自下而上的计算器语法的 CFSM

CFSM for the bottom-up calculator grammar

图 2.26显示了自下而上版本的计算器语法的 CFSM 。状态 6、7、9 和 13 包含潜在的移位-归约冲突，但所有这些冲突都可以通过全局 FOLLOW 集解决。因此，SLR 解析就足够了。例如，在状态 6 中，FIRST( add_op )∩FOLLOW( stmt )=∅。除了移位和归约规则之外，我们还允许解析表作为一种优化来包含“移位然后归约”形式的规则。此优化用于消除示例 2.38中的简单状态，例如 1' 和 0' ，它们只有一个项，末尾带有 •。

The CFSM for our bottom-up version of the calculator grammar appears in Figure 2.26. States 6, 7, 9, and 13 contain potential shift-reduce conflicts, but all of these can be resolved with global FOLLOW sets. SLR parsing therefore suffices. In State 6, for example, FIRST(add_op) ∩ FOLLOW(stmt) = ∅. In addition to shift and reduce rules, we allow the parse table as an optimization to contain rules of the form “shift and then reduce.” This optimization serves to eliminate trivial states such as 1' and 0' in Example 2.38, which had only a single item, with the • at the end.

图 2.27是 CFSM 的图形表示。图 2.28是适合在表驱动解析器中使用的表格表示。图 2.29是（语言无关的）解析器驱动程序的伪代码。图 2.30是解析器对求和平均程序的操作轨迹。■

A pictorial representation of the CFSM appears in Figure 2.27. A tabular representation, suitable for use in a table-driven parser, appears in Figure 2.28. Pseudocode for the (language-independent) parser driver appears in Figure 2.29. A trace of the parser's actions on the sum-and-average program appears in Figure 2.30. ■

处理 Epsilon 作品

Handling Epsilon Productions

例 2.40

Example 2.40

自下而上的计算器语法中的 Epsilon 产生式

Epsilon productions in the bottom-up calculator grammar

细心的读者可能已经注意到，除了对stmt_list、expr和term使用左递归规则之外，图 2.25中的文法还与图 2.16中的文法在另一个方面有所不同：它将stmt_list定义为一个或多个stmts的序列，而不是零个或多个。（这当然意味着它定义了一种不同的语言。）为了表示与图 2.16相同的语言，图 2.25中的产生式 3 ，

The careful reader may have noticed that the grammar of Figure 2.25, in addition to using left-recursive rules for stmt_list, expr, and term, differs from the grammar of Figure 2.16 in one other way: it defines a stmt_list to be a sequence of one or more stmts, rather than zero or more. (This means, of course, that it defines a different language.) To capture the same language as Figure 2.16, production 3 in Figure 2.25,

stmt_list → stmt

stmt_list → stmt

需要替换为

would need to be replaced with

stmt_list → ε

stmt_list → ε

■

■

请注意，通常情况下，语句列表为空是有意义的。在计算器语言中，它只允许一个空程序，这确实很愚蠢。然而，在实际语言中，它允许结构化语句的主体为空，这可能非常有用。人们经常希望 case或多路if…then…else语句的一个分支为空，而空的while循环允许并行程序（或操作系统）等待来自另一个进程或 I/O 设备的信号。

Note that it does in general make sense to have an empty statement list. In the calculator language it simply permits an empty program, which is admittedly silly. In real languages, however, it allows the body of a structured statement to be empty, which can be very useful. One frequently wants one arm of a case or multi-way if… then … else statement to be empty, and an empty while loop allows a parallel program (or the operating system) to wait for a signal from another process or an I/O device.

例 2.41

Example 2.41

带有 epsilon 生成的 CFSM

CFSM with epsilon productions

如果我们查看计算器语言的 CFSM，我们会发现状态 0 是唯一需要更改的状态，以便允许空语句列表。项目

If we look at the CFSM for the calculator language, we discover that State 0 is the only state that needs to be changed in order to allow empty statement lists. The item

stmt_list → • stmt

stmt_list → • stmt

变成

becomes

stmt_list → • ε

stmt_list → • ε

相当于

which is equivalent to

stmt_list → ε •

stmt_list → ε •

或者简单地

or simply

stmt_list → •

stmt_list → •

整个州

The entire state is then

程序→ • stmt_list $$	在stmt_list上移位并转到 2
stmt_list → • stmt_list stmt
stmt_list → •	在 $$ 减少（弹出 0 个状态，在输入时推送stmt_list）
stmt → • id := expr	on id shift 并转到 3
stmt → • 读取 id	读取移位并转到 1
stmt → • 写入expr	写入移位并转到 4

前瞻项目

The look-ahead for item

stmt_list → •

stmt_list → •

是FOLLOW ( stmt_list )，即结束标记$$。由于$$不会出现在此状态下任何其他项目的前瞻中，因此我们的语法仍为 SLR(1)。值得注意的是，epsilon 产生式通常会阻止语法成为 LR(0)：如果此类产生式与点位于终结符之前的项目共享状态，我们将无法在不前瞻的情况下判断是否“识别” ε 。■

is FOLLOW(stmt_list), which is the end-marker, $$. Since $$ does not appear in the look-aheads for any other item in this state, our grammar is still SLR(1). It is worth noting that epsilon productions commonly prevent a grammar from being LR(0): if such a production shares a state with an item in which the dot precedes a terminal, we won't be able to tell whether to “recognize” ε without peeking ahead. ■

检查你的理解

Check Your Understanding

37. 右句子形式的句柄是什么？

37. What is the handle of a right sentential form?

38. 解释特征有限状态机在LR解析中的意义。

38. Explain the significance of the characteristic finite-state machine in LR parsing.

39.  LR 项目中的点 (•) 有何意义？

39. What is the significance of the dot (•) in an LR item?

40.  LR 状态的基础与闭合有何区别？

40. What distinguishes the basis from the closure of an LR state?

41. 什么是移位-归约冲突？在各种 LR 系列解析器中如何解决该问题？

41. What is a shift-reduce conflict? How is it resolved in the various kinds of LR-family parsers?

42. 概述自下而上的解析器驱动程序执行的步骤。

42. Outline the steps performed by the driver of a bottom-up parser.

43.  yacc/bison生成哪种类型的解析器？通过 ANTLR 生成？

43. What kind of parser is produced by yacc/bison? By ANTLR?

44. 为什么在LR(0)语法中从来没有任何epsilon产生式？

44. Why are there never any epsilon productions in an LR(0) grammar?